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

洛谷P1339 [洛谷P1339 [USACO09OCT]热浪Heat Wave(最短路),p1339usaco09oct。USACO09OCT]热浪Heat Wave(最短路),p1339usaco09oct

题材陈述

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).

罗德岛纯朴的民眾们那一个夏季正在受到宏大的暖气!!!他们的Louis安那长角牛吃上去不错,但是他们而不是很专长生產包括乳脂的乳製品。Farmer
John那个时候以先天下之忧而忧,后天下之乐而乐的动感,身体力行地担任起向马萨诸塞运输大批量的养分冰凉的牛奶的职分,以缓和内华达人忍受伏暑的伤痛。

FJ已经商量过可以把牛奶从爱荷华运送到佛罗里达州的门道。这一个路子包含开头点和极端先风流倜傥共通过T
(1 <= T <=
2,500)个城镇,方便地方统一规范明為1到T。除了起源和终端各省各样城镇由两条双向道路连向至少八个其余地乡镇。每条道路有四个透过费用(包括汽油本钱,过路费等等卡塔 尔(英语:State of Qatar)。

给定贰个地图,包括C (1 <= C <=
6,200)条直接连接2个村镇的征程。每条道路由道路的起源中华Vs,终点Re (1 <=
Lacrosses <= T; 1 <= Re <= T),和花费(1 <= Ci <=
1,000)组成。求从开始的市集Ts (1 <= Ts <= T)到顶峰的镇子Te(1 <=
Te <= T)最小的总费用。

输入输出格式

输入格式:

 

率先行: 4个由空格隔离的整数: T, C, Ts, Te

第2到第C+1行: 第i+1行陈诉第i条道路。有3个由空格隔断的整数: 翼虎s, Re和Ci

 

出口格式:

 

三个独门的整数表示从Ts到Te的微小总耗费。数据保障起码存在一条道路。

 

输入输出样例

输入样例#1: 复制

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

输出样例#1: 复制

7

说明

【样例表明】

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

 

 

裸的最短路,更新了一下dijstra的板子

 

[USACO09OCT]热浪Heat
Wave(最短路),p1339usaco09oct 题目汇报 The good folks in Texas are
having a heatwave this summer. Their Texas Longhorn cows make for
good…

相关文章