10517: 强迫症
Memory Limit:128 MB
Time Limit:2.000 S
Judge Style:Text Compare
Creator:
Submit:1
Solved:0
Description
2332933是一个严重的强迫症患者,现在他有一个无向图,这个无向图有n个点,m条边,现在可以修改一些边的长度改成任意非负整数,起点为1号点,终点为n号点。他想知道最少需要修改多少条边,可以使得起点到终点的最短路恰好为c。
Input
第一行T <= 10
接下来每个case:第一行3个整数n m c,(2 <= n <= 100, 1 <= m <= 500, s!=t, 0 <= c <= 1000000),接下来m行每行3个整数,u,v,w(1 <= u,v <= n, u!=v,0 <= w <= 100000),表示u号点到v号点有一条长度为w的边。输入保证s到t连通,保证c不小于原图中1到n的最短路。
接下来每个case:第一行3个整数n m c,(2 <= n <= 100, 1 <= m <= 500, s!=t, 0 <= c <= 1000000),接下来m行每行3个整数,u,v,w(1 <= u,v <= n, u!=v,0 <= w <= 100000),表示u号点到v号点有一条长度为w的边。输入保证s到t连通,保证c不小于原图中1到n的最短路。
Output
每个case输出"Case x: y",x为从1开始的编号,y为对应输入中询问的答案。
Sample Input Copy
1
3 2 1
1 2 10
2 3 1
Sample Output Copy
Case 1: 1
HINT
Author: zhaoweijie12