[USACO09JAN] Safe Travel G

题面翻译

【题目描述】

给定一张有 $n$ 个节点，$m$ 条边的无向图，对于任意的 $i$（$2\le i\le n$），请求出在不经过原来 $1$ 节点到 $i$ 节点最短路上最后一条边的前提下，$1$ 节点到 $i$ 节点的最短路。

特别地，保证 $1$ 到任何一个点 $i$ 的最短路都是唯一的。

保证图中没有重边和自环。

【输入格式】

第一行，两个整数 $n,m$。

之后 $m$ 行，每行三个整数 $a_i,b_i,t_i$ 表示有一条 $a_i$ 到 $b_i$，边权为 $t_i$ 的无向边。

【输出格式】

共 $n-1$ 行，第 $i$ 行表示 $1$ 到 $i+1$ 在不经过原来 $1$ 节点到 $i+1$ 节点最短路上最后一条边的前提下的最短路。如果最短路不存在，则在对应行输出 -1。

翻译贡献者：

题目描述

Gremlins have infested the farm. These nasty, ugly fairy-like

creatures thwart the cows as each one walks from the barn (conveniently located at pasture_1) to the other fields, with cow_i traveling to from pasture_1 to pasture_i. Each gremlin is personalized and knows the quickest path that cow_i normally takes to pasture_i. Gremlin_i waits for cow_i in the middle of the final cowpath of the quickest route to pasture_i, hoping to harass cow_i.

Each of the cows, of course, wishes not to be harassed and thus chooses an at least slightly different route from pasture_1 (the barn) to pasture_i.

Compute the best time to traverse each of these new not-quite-quickest routes that enable each cow_i that avoid gremlin_i who is located on the final cowpath of the quickest route from pasture_1 to

pasture_i.

As usual, the M (2 <= M <= 200,000) cowpaths conveniently numbered 1..M are bidirectional and enable travel to all N (3 <= N <= 100,000) pastures conveniently numbered 1..N. Cowpath i connects pastures a_i (1 <= a_i <= N) and b_i (1 <= b_i <= N) and requires t_i (1 <= t_i <= 1,000) time to traverse. No two cowpaths connect the same two pastures, and no path connects a pasture to itself (a_i != b_i). Best of all, the shortest path regularly taken by cow_i from pasture_1 to pasture_i is unique in all the test data supplied to your program.

By way of example, consider these pastures, cowpaths, and [times]:

1--[2]--2-------+ 
|       |       | 
[2]     [1]     [3] 
|       |       | 
+-------3--[4]--4

TRAVEL     BEST ROUTE   BEST TIME   LAST PATH 
p_1 to p_2       1->2          2         1->2 
p_1 to p_3       1->3          2         1->3 
p_1 to p_4      1->2->4        5         2->4 

When gremlins are present:

TRAVEL     BEST ROUTE   BEST TIME    AVOID 
p_1 to p_2     1->3->2         3         1->2 
p_1 to p_3     1->2->3         3         1->3 
p_1 to p_4     1->3->4         6         2->4 

For 20% of the test data, N <= 200.

For 50% of the test data, N <= 3000.

TIME LIMIT: 3 Seconds

MEMORY LIMIT: 64 MB

输入格式

* Line 1: Two space-separated integers: N and M

* Lines 2..M+1: Three space-separated integers: a_i, b_i, and t_i

输出格式

* Lines 1..N-1: Line i contains the smallest time required to travel from pasture_1 to pasture_i+1 while avoiding the final cowpath of the shortest path from pasture_1 to pasture_i+1. If no such path exists from pasture_1 to pasture_i+1, output -1 alone on the line.

样例 #1

样例输入 #1

4 5 
1 2 2 
1 3 2 
3 4 4 
3 2 1 
2 4 3

样例输出 #1

3 
3 
6