P10305: 摧毁巴士站
传统题
1.000s
时间限制
128MB
内存限制
2 提交
2 解决
【题目描述】
Gabiluso是最伟大的间谍之一。现在，他试图完成一个“不可能完成”的使命――减缓Colugu的军队到达机场的时间。Colugu有n个公共汽车站和m条道路。每条道路直接连接两个巴士站，所有的道路都是单向的。为了保持空气洁净，政府禁止所有军用车辆，因此，军队必须乘搭巴士去机场。两个巴士站之间，可能有超过一条道路。如果一个公共汽车站被破坏时，所有连接该站的道路将无法运作。Gabiluso需要做的是摧毁了一些公共汽车站，使军队无法在K分钟内到达机场。一辆公交车通过一条道路，都是一分钟。所有巴士站的编号从1到n。1号巴士站是在军营，第n号站是机场。军队始终从第一站出发。第一站和第n站不能被破坏，这里有大量的防御力量。当然也没有从第一站到第n站的道路。
请帮助Gabiluso来计算能完成使命所需摧毁的最低数目的巴士站。 【输入】
第一行包含三个整数n，m，k
(2<n<=50,0<m<=4000,0<k<1000)。
接下来m行，每行2个整数s和f，表示从站s到站f有一条路。
【输出】
输出最少需要摧毁的巴士站数目。
【样例输入】复制
5 7 3
1 3
3 4
4 5
1 2
2 5
1 4
4 5
【提示】
【数据规模】
30%的数据N<=15。