比赛场次 89
比赛名称 20110414pm
比赛状态 已结束比赛成绩
开始时间 2011-04-14 14:30:00
结束时间 2011-04-14 17:30:00
开放分组 全部用户
注释介绍
题目名称 龙凡
输入输出 travel.in/out
时间限制 3000 ms (3 s)
内存限制 64 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
GravatarPom ATAATTTTTT 0.000 s 0.00 MiB 30
Gravatarybh ATATTTTTTT 0.000 s 0.00 MiB 20
Gravatarreamb AEATTTEEEE 0.000 s 0.00 MiB 20
GravatarCitron酱 AEWAWWTTET 0.000 s 0.00 MiB 20
Gravatarwo shi 刘畅 AEWTTTTEEE 0.000 s 0.00 MiB 10
Gravatar.Xmz ATWWWWWWTT 0.000 s 0.00 MiB 10
Gravatar苏轼 ATWTTTTTTT 0.000 s 0.00 MiB 10
Gravatarkaaala WWWWWWWWWW 0.000 s 0.00 MiB 0

龙凡

★★★☆   输入文件: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

输出解释:

跟题中例子相同