ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1450. Russian Pipelines

Wtf is wrong with Test #3 ?!?!?!??! Dijkstra not working here???
Posted by Luka Bulatovic 21 Aug 2011 03:13
I did Dijkstra algorithm for S to F, but seems to exceeds time on test #3 ? Anyone got a clue? Tnx in advance
Re: Wtf is wrong with Test #3 ?!?!?!??! Dijkstra not working here???
Posted by Leonid (SLenik) Andrievskiy 16 Sep 2011 04:58
Well, I do not know what this test is, but the answer for this test is "No solution".
Re: Wtf is wrong with Test #3 ?!?!?!??! Dijkstra not working here???
Posted by Smilodon_am [Obninsk INPE] 8 Dec 2018 02:11
I don't know how to solve this problem with Dijkstra algorithm.

My approach is another.

Perhaps one pair of tests below can help you to understand the problem more clearely:

7 7
1 2 10
2 3 10
3 4 5
1 5 1
5 6 50
6 7 50
7 3 50
1 4
ans:
156


7 7
1 2 10
2 3 10
3 4 5
1 5 50
5 6 50
6 7 50
7 3 50
1 4
ans:
205
Re: Wtf is wrong with Test #3 ?!?!?!??! Dijkstra not working here???
Posted by Markfryazino 29 Jan 2019 17:38
What you need to do is to find the path with maximum weights of all edges while Dijkstra tries to find minimum. You're solving the wrong problem.