OI题库

【问题描述】

    小x在玩一款塔防类游戏。游戏的规则如下：

1） 整个地图由N个交汇点，M条双向的道路组成；

2） 怪物出现的地点为S，终点为T；

3） 怪物通过每段小路都要一定的时间；

这个游戏的任务不是把怪物消灭，而是延缓怪物到达终点的时间。小x唯一的道具是路障，一个路障可以减缓通过这段路的所有怪物一个单位时间。所以怪物从起点到达终点的时间就是 没有路障他们通过所有路径经过的时间+ 路径上 路障的个数。

游戏中的怪物是很聪明的，他们会在出发前侦查到每段路上的路障个数，然后选择总时间最短的路径。

小x现在想知道最少需要多少个路障，才能使得怪物从起点到终点的时间变长。

【输入】

       第一行：N，M，S和T，具体含义如题目描述。N个交汇点的编号范围是1..N。

接下来M行，每行三个整数A，B，C。表示A到B之间有一条小路相连，且通过它需要的时间为C。

输入数据保证两点最多只有一条道路相连，且S到T必然存在路径。

【输出】

       一个整数，表示S到T之间最短路增长所需要最小的路障的数目。

【输入输出样例1】

5 5 1 5
1 2 1
2 3 3
1 4 2
4 3 2
5 1 1

1

【输入输出样例2】

6 11 2 5
2 3 1
2 1 4
2 6 2
5 4 11
5 1 16
5 6 18
4 1 5
4 6 7
3 1 3
3 6 1
1 6 2

3 

【数据范围】

30%  N<=10,M<=50

50%  N<=200,M<=100000

30%  N<=1000,M<=499500  0