| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank Statistics |
Problem G
最短路径
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 |