OpenJudge

2:floyd求最短路径

总时间限制:
10000ms
内存限制:
1000kB
描述

给出一个有向图的结构,求所有顶点间的最短路径

输入
若干行整数,第一行有2个数,分别为顶点数v和弧数a,接下来有a行,每一行有3个数,分别是该条弧所关联的两个顶点编号和弧的权值
输出
若干行
每行第一个为一个整数,为最短路径值,其余为若干个空格隔开的顶点构成的最短路径序列(用小写字母)
若无最短路径,直接输出no answer
样例输入
3 5
0 1 4
0 2 11
1 0 6
1 2 2
2 0 3
样例输出
4 v0 v1
6 v0 v1 v2
5 v1 v2 v0
2 v1 v2
3 v2 v0
7 v2 v0 v1
全局题号
4867
添加于
2012-05-31
提交次数
227
尝试人数
113
通过人数
95