USACO 2009 9th 熱浪 heatwv 解題報告

USACO/heatwv

第九題: 熱浪 [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)

【分析】

 USACO竟然有這麼裸的最短路題目，汗，最後還說漏嘴了～

 就是一個裸最短路，Dijkstra、SPFA都能迅速解決，所以直接套用經典算法即可。

由於頂點數為2500，所以Floyd算法會超時。

我用C++ STL寫的SPFA，10測測試點共0.03s無壓力。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25440

01 /*
02 *Problem: USACO 2009 9th Heatwv
03 *Author: Yee-fan Zhu
04 *Method: Shortest-Path
05 *GTalk: zyfworks@gmail.com
06 */
07 #include <cstdio>
08 #include <cstdlib>
09 #include <vector>
10 #include <cstring>
11 #include <queue>
12 using namespace std;
13 const int MAXN=2501;
14 typedef vector<int> Vec;
15 Vec Map[MAXN],Val[MAXN];
16 int N,M,S,T;
17
18 void init()
19 {
20     scanf("%d %d %d %d\n",&N,&M,&S,&T);
21    
22     int a,b,v;
23     for(int i=1;i<=M;i++)
24     {
25         scanf("%d %d %d\n",&a,&b,&v);
26         Map[a].push_back(b);
27         Val[a].push_back(v);
28         Map[b].push_back(a);
29         Val[b].push_back(v);
30     }
31 }
32
33 int dist[MAXN];
34 int flag[MAXN];
35 const int INF=1000000000;
36 queue<int>Q;
37 void SPFA()
38 {
39     for(int i=1;i<=N;i++)
40         dist[i]=INF,flag[i]=0;
41     dist[S]=0,flag[S]=1;
42     Q.push(S);
43     int t,tmp;
44     while(!Q.empty())
45     {
46         t=Q.front();
47         Q.pop();
48         flag[t]=0;
49         for(unsigned int i=0;i<Map[t].size();i++)
50         {
51             tmp=dist[t]+Val[t][i];
52             if(tmp<dist[Map[t][i]])
53             {
54                 dist[Map[t][i]]=tmp;
55                 if(!flag[Map[t][i]])
56                 {
57                     Q.push(Map[t][i]);
58                     flag[Map[t][i]]=1;
59                 }
60             }
61         }
62     }
63     printf("%d\n",dist[T]);
64     return;
65 }
66
67 int main()
68 {
69     freopen("heatwvx.in","r",stdin);
70     freopen("heatwvx.out","w",stdout);
71     init();
72     SPFA();
73     return 0;
74 }