传送门

★☆   输入文件：heatwvx.in   输出文件：heatwvx.out   简单对比
　　　　　　时间限制：1 s   内存限制：128 MB

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

裸SPFA

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 using namespace std;
 5 #define maxm 6205
 6 #define maxn 2505
 7 #define inf 0x7f
 8 queue<int>q;
 9 struct Edge {
10     int u,v,w,next;
11     Edge (int u=0,int v=0,int w=0,int next=0):u(u),v(v),w(w),next(next) {}
12 }edge[maxm*2];
13 int dis[maxn],head[maxn],cnt=0;
14 bool inq[maxn]={0};
15 void Add_edge(int u,int v,int w) {
16     edge[++cnt]=Edge(u,v,w,head[u]);
17     head[u]=cnt;
18 }
19 int main() {
20     freopen("heatwvx.in","r",stdin);
21     freopen("heatwvx.out","w",stdout);
22     int n,m,s,t;
23     scanf("%d%d%d%d",&n,&m,&s,&t);
24     for(int i=1;i<=m;i++) {
25         int u,v,w;
26         scanf("%d%d%d",&u,&v,&w);
27         Add_edge(u,v,w);
28         Add_edge(v,u,w);
29     }
30     memset(dis,inf,sizeof(dis));
31     dis[s]=0;q.push(s);inq[s]=true;
32     while(!q.empty()) {
33         int u=q.front();q.pop();inq[u]=false;
34         for(int i=head[u];i;i=edge[i].next) {
35             int v=edge[i].v;
36             if(dis[v]>edge[i].w+dis[u]) {
37                 dis[v]=edge[i].w+dis[u];
38                 if(!inq[v]) {
39                     inq[v]=true;
40                     q.push(v);
41                 }
42             }
43         }
44     }
45     printf("%d",dis[t]);
46     fclose(stdin);fclose(stdout);
47     return 0;
48 }

cogs 397. [USACO Oct09] 热浪