OpenJudge

3:校园规划

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

学校现在碰到了一个难题,就是如何减少下课拥堵问题,现在给你n个点,m条边。0点(零)是教学楼,n-1点是食堂,每一条路的长度是单位1,每一条路有一个容量flow表示这一条路在任意单位时间段里最多只能同时有flow个人。现在有k个人,问你最少要多少时间,这样k个人都可以到食堂?

输入
有几个测试用例,请处理直到EOF。 每个测试用例的第一行包含三个整数N(2 <= N <= 2500),M(0 <= M <= 5000),K(0 <= K <= 109)。 然后跟随M行,每行都有三个数字ai,bi,ci(0 <= ci <= 20),意味着从顶点ai到bi的边具有容量ci。
输出
对于每个测试用例,打印整数代表最小时间。 如果无法满足要求,请打印“No solution”(不含引号)。
样例输入
5 6 4
0 1 2
0 3 1
1 2 1
2 3 1
1 4 1
3 4 2
3 3 10
0 1 1
1 2 1
0 2 1
2 0 1
样例输出
3
6
No solution
全局题号
14713
提交次数
2
尝试人数
1
通过人数
1