USACO/block

来自NOCOW

3

[编辑] 题目描述

贝丝最近搬家到了一个小农场，但她经常回去拜访一些老朋友。她喜欢在户外游玩，不想太快到达自己的老屋子。于是她决定选取第二短的路。郊外游R(1 <= R <= 100,000)条双向路，每个连接着N (1 <= N <= 5000) 个节点，标记做1到N。贝丝从节点1出发，而她的朋友在节点N。第二短路可以与最短路径有公共路径，并且可以把某段路走多遍。

[编辑] 输入格式:

第一行: 两个整数 N 和 R
第2到R+1行: 每行3个整数 A B D 表示从A到B的路长为D(1 <= D <= 5000)

[编辑] 样例输入(file block.in):

[编辑] 输出格式:

第一行: 第二短路

[编辑] 样例输出(file block.out):

[编辑] 输出说明:

最短路: 1 -> 2 -> 4 (长度：100+200=300)

次短：1 -> 2 -> 3 -> 4 (长度：100+250+100=450)

译题： wsmlby@gmail.com

Roadblocks [Mirek Michalski, 2004]

Bessie has moved to a small farm and sometimes enjoys returning to
visit one of her best friends. She does not want to get to her old
home too quickly, because she likes the scenery along the way. She
has decided to take the second-shortest rather than the shortest
path. She knows there must be some second-shortest path.

The countryside consists of R (1 <= R <= 100,000) bidirectional
roads, each linking two of the N (1 <= N <= 5000) intersections,
conveniently numbered 1..N. Bessie starts at intersection 1, and
her friend (the destination) is at intersection N.

The second-shortest path may share roads with any of the shortest
paths, and it may backtrack i.e., use the same road or intersection
more than once. The second-shortest path is the shortest path whose
length is longer than the shortest path(s) (i.e., if two or more
shortest paths exist, the second-shortest path is the one whose
length is longer than those but no longer than any other path).

PROBLEM NAME: block

INPUT FORMAT:

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

* Lines 2..R+1: Each line contains three space-separated integers: A,
        B, and D that describe a road that connects intersections A
        and B and has length D (1 <= D <= 5000)

SAMPLE INPUT (file block.in):

4 4
1 2 100
2 4 200
2 3 250
3 4 100


OUTPUT FORMAT:

* Line 1: The length of the second shortest path between node 1 and
        node N

SAMPLE OUTPUT (file block.out):

450

OUTPUT DETAILS:

Two routes: 1 -> 2 -> 4 (length 100+200=300) and 1 -> 2 -> 3 -> 4
(length 100+250+100=450)