I have the same problem and I don't know why.
If somebody know this test or some other like that, please show it.

I supose that there is only one test... But all what you need is delete one road between 2 points and with help of Deikstra find out the shortest way between this points ... than add length of road and you find out the shortest way throw this row.... and so on! I solved this problem such way!

It's O(N^4)! You can optimize this nice idea to reach O(N^3)!

here is test 1:
4 6
1 2 40
1 3 50
1 40 60
2 3 10
2 4 30
3 4 20

one answer: 2 3 4

Edited by author 21.10.2005 16:50

Thank you very much!

Thanks for your test... :)
I have AC 0.046 sec...

but this problem says:
"...In the town there are N crossing points numbered from 1 to N..."

My program prints:
2 4 3
It's true, imho.

Floyd Algrathm is also advisable. However, please take note of another test:
4 4
1 2 10
2 3 1
3 4 1
4 1 1
should output things like 1 4 3 2
but NOT 1 4 3 4

my ans is 2 3 4,but get WA at Test#1

I think It's :
1 2 40
1 3 50
1 4 60
2 3 10
2 4 30
3 4 20

Impossible. I get 2 3 4 as answer at get wrong answer on #1