网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[USACO Oct09]热浪
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | heatwvx.in | 输出文件 | heatwvx.out |
第九題: 熱浪 [300分] [Rob Kolstad (傳統題目), 2009]
德克薩斯純樸的民眾們這個夏天正在遭受巨大的熱浪!!!他們的德克薩斯長角牛吃起來不錯,
可是他們並不是很擅長生產富含奶油的乳製品。Farmer John此時以先天下之憂而憂,後天下
之樂而樂的精神,身先士卒地承擔起向德克薩斯運送大量的營養冰涼的牛奶的重任,以減輕德
克薩斯人忍受酷暑的痛苦。
FJ已經研究過可以把牛奶從威斯康星運送到德克薩斯州的路線。這些路線包括起始點和終點先
一共經過T (1 <= T <= 2,500)個城鎮,方便地標號為1到T。除了起點和終點外地每個城鎮
由兩條雙向道路連向至少兩個其它地城鎮。每條道路有一個通過費用(包括油費,過路費等等)。
考慮這個有7個城鎮的地圖。城鎮5是奶源,城鎮4是終點(括號內的數字是道路的通過費用)。
[1]----1---[3]-
/ \
[3]---6---[4]---3--[3]--4
/ / /|
5 --[3]-- --[2]- |
\ / / |
[5]---7---[2]--2---[3]---
| /
[1]------
經過路線5-6-3-4總共需要花費3 (5->6) + 4 (6->3) + 3 (3->4) = 10的費用。
給定一個地圖,包含C (1 <= C <= 6,200)條直接連接2個城鎮的道路。每條道路由道路的
起點Rs,終點Re (1 <= Rs <= T; 1 <= Re <= T),和花費(1 <= Ci <= 1,000)組
成。求從起始的城鎮Ts (1 <= Ts <= T)到終點的城鎮Te(1 <= Te <= T)最小的總費用。
分值: 300
題目名稱: heatwv
輸入格式:
* 第一行: 4個由空格隔開的整數: T, C, Ts, Te
* 第2到第C+1行: 第i+1行描述第i條道路。有3個由空格隔開的整數: Rs, Re和Ci
樣例輸入 (文件 heatwv.in):
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
輸入細節:
跟題目描述的地圖一致。
輸出格式:
* 第一行: 一個單獨的整數表示Ts到Te的最短路的長度。(不是費用麼?怎麼突然變直白了
——譯者注)數據保證至少存在一條道路。
樣例輸出 (文件 heatwv.out):
7
輸出細節:
5->6->1->4 (3 + 1 + 3)