1540: 最短路径--Dijkstra
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:60
解决:36
题目描述
有向图中某一顶点到其余各顶点的最短路径。带权图的最短路径是指两点间的路径中边权和最小的路径。


输入
输入有多个带权有向图的情况。每种情况先输入一行正整数m、n,分别表示有m个顶点、n条有向弧。顶点序号从0开始。接着有n行,每行3个正整数表示弧尾、弧头、权值。
输出
求出v0到图中其余每个顶点的路径及最短路径值,如果顶点i到顶点j,无路径输出vi->vj 无最短路径。
样例输入 复制
6 11
0 1 50
0 2 10
0 4 45
1 4 10
1 2 15
2 0 20
2 3 15
3 1 20
3 4 35
4 3 30
5 3 3
样例输出 复制
v0->v2->v3->v1 45
v0->v2 10
v0->v2->v3 25
v0->v4 45
v0->v5 无最短路径