# 洛谷P1339 [USACO09OCT]热浪Heat Wave(最短路)

2018-02-27 08:59:49来源:cnblogs.com作者:自为风月马前卒人点击

## 题目描述

The good folks in Texas are having a heatwave this summer. Their Texas Longhorn cows make for good eating but are not so adept at creating creamy delicious dairy products. Farmer John is leading the charge to deliver plenty of ice cold nutritious milk to Texas so the Texans will not suffer the heat too much.

FJ has studied the routes that can be used to move milk from Wisconsin to Texas. These routes have a total of T (1 <= T <= 2,500) towns conveniently numbered 1..T along the way (including the starting and ending towns). Each town (except the source and destination towns) is connected to at least two other towns by bidirectional roads that have some cost of traversal (owing to gasoline consumption, tolls, etc.). Consider this map of seven towns; town 5 is the

source of the milk and town 4 is its destination (bracketed integers represent costs to traverse the route):

``                              [1]----1---[3]-                             /               /                      [3]---6---[4]---3--[3]--4                     /               /       /|                    5         --[3]--  --[2]- |                     /       /        /       |                      [5]---7---[2]--2---[3]---                            |       /                           [1]------``

Traversing 5-6-3-4 requires spending 3 (5->6) + 4 (6->3) + 3 (3->4) = 10 total expenses.

Given a map of all the C (1 <= C <= 6,200) connections (described as two endpoints R1i and R2i (1 <= R1i <= T; 1 <= R2i <= T) and costs (1 <= Ci <= 1,000), find the smallest total expense to traverse from the starting town Ts (1 <= Ts <= T) to the destination town Te (1 <= Te <= T).

FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 <= T <= 2,500)个城镇，方便地标号為1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用（包括油费，过路费等等）。

## 输入输出样例

`7 11 5 42 4 21 4 37 2 23 4 35 7 57 3 36 1 16 3 42 4 35 6 37 2 1`

`7`

## 说明

【样例说明】

5->6->1->4 (3 + 1 + 3)