1557 熱浪

1557 熱浪

德克薩斯純樸的民眾們這個夏天正在遭受巨大的熱浪！！！他們的德克薩斯長角牛吃起來不錯，可是他們並不是很擅長生產富含奶油的乳製品。Farmer John此時以先天下之憂而憂，後天下之樂而樂的精神，身先士卒地承擔起向德克薩斯運送大量的營養冰涼的牛奶的重任，以減輕德克薩斯人忍受酷暑的痛苦。

FJ已經研究過可以把牛奶從威斯康星運送到德克薩斯州的路線。這些路線包括起始點和終點先一共經過T (1 <= T <= 2,500)個城鎮，方便地標號為1到T。除了起點和終點外地每個城鎮由兩條雙向道路連向至少兩個其它地城鎮。每條道路有一個通過費用（包括油費，過路費等等）。

給定一個地圖，包含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)最小的總費用。

第一行: 4個由空格隔開的整數: T, C, Ts, Te

第2到第C+1行: 第i+1行描述第i條道路。有3個由空格隔開的整數: Rs, Re和Ci

一個單獨的整數表示從Ts到Te的最小總費用。數據保證至少存在一條道路。

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

7

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

分類標簽 Tags 點此展開

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 const int MAXN=30001;
 7 const int maxn=0x7fffffff;
 8 struct node
 9 {
10     int u;
11     int v;
12     int w;
13     int next;
14 }edge[MAXN]; 
15 int num=1;
16 int head[MAXN];
17 int n,m,begin,end;
18 int dis[MAXN];
19 int vis[MAXN];
20 void spfa()
21 {
22     for(int i=1;i<=n;i++)dis[i]=maxn;
23     queue<int>q;
24     vis[begin]=1;
25     q.push(begin);
26     dis[begin]=0;
27     while(q.size()!=0)
28     {
29         int p=q.front();
30         q.pop();
31         vis[p]=0;
32         for(int i=head[p];i!=-1;i=edge[i].next)
33         {
34             if(dis[edge[i].v]>dis[p]+edge[i].w&&dis[p]!=maxn)
35             {
36                 dis[edge[i].v]=dis[p]+edge[i].w;
37                 if(vis[edge[i].v]==0)
38                 {
39                     q.push(edge[i].v);
40                     vis[edge[i].v]=1;
41                 }
42             }
43         }
44     }
45     printf("%d",dis[end]);
46 }
47 int main()
48 {
49     scanf("%d%d%d%d",&n,&m,&begin,&end);
50     for(int i=1;i<=n;i++)head[i]=-1;
51     for(int i=1;i<=m;i++)
52     {
53         scanf("%d%d%d",&edge[num].u,&edge[num].v,&edge[num].w);
54         edge[num].next=head[edge[num].u];
55         head[edge[num].u]=num++;
56         edge[num].w=edge[num-1].w;
57         edge[num].u=edge[num-1].v;
58         edge[num].v=edge[num-1].u;
59         edge[num].next=head[edge[num].u];
60         head[edge[num].u]=num++;
61     }
62     spfa();
63     return 0;
64 }