1032 : 加速通道
时间限制Time Limit
1
秒Sec
内存限制Memory Limit
128
兆MB
提交次数Submitted
69 次Times
通过次数Solved
28 次Times
标准评测 Standard
从标准输入读入,结果写到标准输出。评测将输出拆成 token,与标准答案逐项比较,不按整段逐字节比对。
Read from standard input and write to standard output. The judge splits the output into tokens and compares them with the official answer; it does not compare raw bytes.
| 比对Compare | token 相同即通过。中间的空格、制表符、换行可多可少。Matching tokens pass. Extra spaces, tabs, or newlines between them are ignored. |
|---|---|
| 不同则错Differs | token 个数或内容不同即错误。23 与 2 3、02 与 2、2.0 与 2 均视为不同。A different token count or value is wrong. 23 vs 2 3, 02 vs 2, and 2.0 vs 2 all differ. |
| 输入Input | 标准输入,格式见题面。Standard input; format as in the statement. |
| 输出Output | 标准输出。Standard output. |
题目描述Description
小明经常看到机场、地铁站会有平地上的“电梯”方便运大行李的旅客节省体力。他想,如果给学校的连廊也装一个,岂不是很有意思。
已知连廊的起点、终点,以及每个路口和路口之间道路的行走时间。安装加速通道的道路,行走时间减半(除法向下取整) 。
假设 只能给一条道路安装加速通道 ,装在哪条道路,能让起点到终点的时间最短呢?帮小明计算一下安装加速通道后通过连廊的最短时间。
输入格式Input
不超过50组测试数据,每组测试数据第一行两个整数:n,m 分别表示路口数和道路数。
接下来 m 行,每行三个数 s,e, t (1 <= s < e <= n,1 <= t <= 10^6)表示 s 与 e 之间有一条双向道路,该道路安装加速通道前所需行走时间为t。
其中起点编号为 1,终点编号为 n。
2 <= n <= 100,1 <= m <= 2000。
数据保证起点与终点连通。
输出格式Output
每组数据输出一行,一个整数,表示加装加速通道后起点到终点的最短时间。
样例Sample
出题Author
CSGrandeur