1557 熱浪 1557 熱浪 時間限制: 1 s 空間限制: 256000 KB 題目等級 : 鑽石 Diamond 時間限制: 1 s 空間限制: 256000 KB 題目等級 : 鑽石 Diamond 時間限制: 1 s 時間限制: 1 s 空間限制: 256000 KB 空間限制: 2560 ...
1557 熱浪
時間限制: 1 s 空間限制: 256000 KB 題目等級 : 鑽石 Diamond 題目描述 Description
德克薩斯純樸的民眾們這個夏天正在遭受巨大的熱浪!!!他們的德克薩斯長角牛吃起來不錯,可是他們並不是很擅長生產富含奶油的乳製品。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)最小的總費用。
輸入描述 Input Description第一行: 4個由空格隔開的整數: T, C, Ts, Te
第2到第C+1行: 第i+1行描述第i條道路。有3個由空格隔開的整數: Rs, Re和Ci
輸出描述 Output Description一個單獨的整數表示從Ts到Te的最小總費用。數據保證至少存在一條道路。
樣例輸入 Sample Input7 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
樣例輸出 Sample Output7
數據範圍及提示 Data Size & Hint5->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 }