5627: 强迫症
内存限制：128 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
2332933是一个严重的强迫症患者，现在他有一个无向图，这个无向图有n个点，m条边，现在可以修改一些边的长度改成任意非负整数，起点为1号点，终点为n号点。他想知道最少需要修改多少条边，可以使得起点到终点的最短路恰好为c。
输入
第一行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的最短路。
输出
每个case输出"Case x: y",x为从1开始的编号，y为对应输入中询问的答案。
样例输入 复制
1
3 2 1
1 2 10
2 3 1
样例输出 复制
Case 1: 1
提示
Author: zhaoweijie12