【題目描述】

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

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

給定一個地圖，包含C (1 ≤ C ≤ 6,200)條直接連接2個城鎮(zhèn)的道路。每條道路由道路的起點Rs，終點Re (1 ≤ Rs ≤ T; 1 ≤ Re ≤ T)，和花費(1 ≤ Ci ≤ 1,000)組成。求從起始的城鎮(zhèn)Ts (1 ≤ Ts ≤ T)到終點的城鎮(zhèn)Te(1 ≤ Te ≤ T)最小的總費用。

【輸入】

第一行: 4個由空格隔開的整數(shù): T, C, Ts, Te;

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

【輸出】

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

【輸入樣例】

?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

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<set> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 3001 #define MOD 123 #define E 1e-6 using namespace std; struct node{int pre;int next;int w; }a[N*10]; int head[N],vis[N],f[N]; int cnt; void add(int x,int y,int w) {cnt++;a[cnt].pre=y;a[cnt].next=head[x];a[cnt].w=w;head[x]=cnt;cnt++;a[cnt].pre=x;a[cnt].next=head[y];a[cnt].w=w;head[y]=cnt; } int main() {int t,c,start,endd;cin>>t>>c>>start>>endd;for(int i=1;i<=c;i++){int x,y,w;cin>>x>>y>>w;add(x,y,w);}memset(f,INF,sizeof(f));f[start]=0;for(int i=1;i<=t;i++){int x=0;int minn=INF;for(int j=1;j<=t;j++)if(vis[j]==0&&f[j]<minn){minn=f[j];x=j;}vis[x]=1;int k=head[x];while(k!=0){int y=a[k].pre;if(vis[y]==0&&f[x]+a[k].w<f[y])f[y]=f[x]+a[k].w;k=a[k].next;}}cout<<f[endd]<<endl;return 0; }

?

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的热浪（信息学奥赛一本通-T1379）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。