比赛场次 | 144 |
---|---|
比赛名称 | 20120705 |
比赛状态 | 已结束比赛成绩 |
开始时间 | 2012-07-05 08:00:00 |
结束时间 | 2012-07-05 12:00:00 |
开放分组 | 全部用户 |
注释介绍 | 2012暑假培训A班 |
题目名称 | 塔防游戏 |
---|---|
输入输出 | defence.in/out |
时间限制 | 1000 ms (1 s) |
内存限制 | 128 MiB |
测试点数 | 10 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
Czb。 | AAAAAAAAAA | 0.000 s | 0.00 MiB | 100 |
CC | AAAAAAAAAA | 0.000 s | 0.00 MiB | 100 |
SnowDancer | AAAAAATAAA | 0.000 s | 0.00 MiB | 90 |
czp | AAAAAATAAA | 0.000 s | 0.00 MiB | 90 |
fuhao | AAWAAWAAAA | 0.000 s | 0.00 MiB | 80 |
Citron酱 | AAWATWTAAA | 0.000 s | 0.00 MiB | 60 |
zhangchi | AAEEEETEAA | 0.000 s | 0.00 MiB | 40 |
wo shi 刘畅 | WWWWWWWWWW | 0.000 s | 0.00 MiB | 0 |
isabella | WWWWWTTWWW | 0.000 s | 0.00 MiB | 0 |
IMSL77 | MMMMMMMMMM | 0.000 s | 0.00 MiB | 0 |
【问题描述】
小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】
defence.in |
defence.out |
5 5 1 5 1 2 1 2 3 3 1 4 2 4 3 2 5 1 1
|
1
{起点到终点的最短路是1到5的道路,所以直接一个路障就可以了。} |
【输入输出样例2】
defence.in |
defence.out |
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
{1—5,4—5,6—5 都+1就可满足,当然还会有其他方案。} |
【数据范围】
30% N<=10,M<=50
50% N<=200,M<=100000
30% N<=1000,M<=499500 0