[Login|Register]
Problems

Status

Rank

Problem 1217
最短路径
Time Limit: 3000ms
Memory Limit: 65536kb
Description
最短路径问题是图论中的经典问题。在实际的应用中,最短路径问题还有各种各样的变型,这里需要你解决的就是其中一个:
给定一个有向图G=(V,E),E中的每条边都有可正可负的权值,表示距离。指定V中的两个顶u和w,请求出从u到w恰好含有k条边的最短路径。注意,路径可以重复经过同一条边。
Input
输入包含多组数据。
每组数据第一行包含三个整数, n, m, k,表示图中顶的数量,边的数量和最短路径的边数 (1≤n≤100, 0≤m≤n2, 1≤k≤109)
第二行包含两个整数u和w,表示起点和终点的编号。顶的编号在1到n之间。
其后m行,每行包含三个整数a, b, c,表示从编号为a的顶到编号为b的顶有一条权为c的边。输入保证没有重边,c的绝对值不超过1000。
输入以n=m=k=0结束,不要处理这组数据。
Output
对每组输入数据输出从u到w恰含k条边的最短路径长度,如果不存在这样的路径则输出”None”。注意答案可能会超过32位整型的范围。
Sample Input
1 1 2
1 1
1 1 1
2 2 999999999
1 2
1 2 1000
2 1 -100
2 2 1000000000
1 1
1 2 1000
2 1 -100
3 3 4
1 2
1 2 -1
2 3 1
3 1 1
3 3 5
1 2
1 2 -1
2 3 1
3 1 1
0 0 0
Sample Output
2
450000000100
450000000000
0
None
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.5ms with 1 query(s).