龙凡
★★★☆
输入文件:
travel.in
输出文件:
travel.out
简单对比
时间限制:3 s
内存限制:64 MiB
[龙凡, 2008]
Gremlins最近在农场上泛滥,它们经常会阻止牛们从农庄(牛棚_1)走到别的牛棚(牛_i的目的
地是牛棚_i).每一个gremlin只认识牛_i并且知道牛_i一般走到牛棚_i的最短路经.所以它
们在牛_i到牛棚_i之前的最后一条牛路上等牛_i. 当然,牛不愿意遇到Gremlins,所以准备找
一条稍微不同的路经从牛棚_1走到牛棚_i.所以,请你为每一头牛_i找出避免gremlin_i的最
短路经的长度.
和以往一样, 农场上的M (2 <= M <= 200,000)条双向牛路编号为1..M并且能让所有牛到
达它们的目的地, N(3 <= N <= 100,000)个编号为1..N的牛棚.牛路i连接牛棚a_i
(1 <= a_i <= N)和b_i (1 <= b_i <= N)并且需要时间t_i (1 <=t_i <= 1,000)通过.
没有两条牛路连接同样的牛棚,所有牛路满足a_i!=b_i.在所有数据中,牛_i使用的牛棚_1到牛
棚_i的最短路经是唯一的.
以下是一个牛棚,牛路和时间的例子:
1--[2]--2-------+
| | |
[2] [1] [3]
| | |
+-------3--[4]--4
行程 最佳路经 最佳时间 最后牛路
p_1 到 p_2 1->2 2 1->2
p_1 到 p_3 1->3 2 1->3
p_1 到 p_4 1->2->4 5 2->4
当gremlins进入农场后:
行程 最佳路经 最佳时间 避免
p_1 到 p_2 1->3->2 3 1->2
p_1 到 p_3 1->2->3 3 1->3
p_1 到 p_4 1->3->4 6 2->4
20%的数据满足N<=200.
50%的数据满足N<=3000.
时间限制: 3秒
内存限制: 64 MB
PROBLEM NAME: travel
输入格式:
* 第一行: 两个空格分开的数, N和M
* 第2..M+1行: 三个空格分开的数a_i, b_i,和t_i
样例输入 (travel.in):
4 5
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3
输入解释:
跟题中例子相同
输出格式:
* 第1..N-1行: 第i行包含一个数:从牛棚_1到牛棚_i+1并且避免从牛棚1到牛棚i+1最
短路经上最后一条牛路的最少的时间.如果这样的路经不存在,输出-1.
样例输出 (travel.out):
3
3
6
输出解释:
跟题中例子相同