[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$ 节点最短路上最后一条边的前提下的最短路。
翻译贡献者:@[cryozwq](/user/282751)。
题目描述
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]:
```cpp
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:
```cpp
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
4 5
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3
输出样例 #1
3
3
6
说明
感谢 karlven 提供翻译。