|
|
вернуться в форумI did Dijkstra algorithm for S to F, but seems to exceeds time on test #3 ? Anyone got a clue? Tnx in advance Well, I do not know what this test is, but the answer for this test is "No solution". 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 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. I was getting TLE 16 with inversed SPFA (longest path) when using DFS.
Switched to BFS (queue instead of recursion) and got AC. |
|
|
