Codeforces 20C Dijkstra?

题目的要求是求一个可能含有自连环和平行边的图的单源最短路（从 1 到 n）。

顶点数为 n, 边数为 m, 2 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁵. 时间限制 2 秒。

原题地址：http://codeforces.com/problemset/problem/20/C

输入数据第一行是 n m, 第二行 u v w, 表示有边 (u, v) 的权值是 w.

输入 1:

5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1

输出 1:

1 4 3 5

这个显然 Dijkstra… 是不太合适的啦。边数有点少，用 SPFA 比较好。注意这道题要求的是求出路径，而不是最短路的数值。