OI题库

安全路经 [龙凡, 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

输出解释:

跟题中例子相同