傳送門

?

題目描述?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 Input

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

樣例輸出?Sample Output

7

數據范圍及提示?Data Size & Hint

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

?

題解：spfa裸題。

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #define ll long long #define N 2600 #define M 6210 using namespace std; int T,C,Ts,Te,Head(0),Tail(0),num(0); int team[M],head[N]={0},dis[N]; bool f[N]={0}; struct node {int v,t,pre; }e[2*M]; void add(int from,int to,int dis) {e[++num].v=to;e[num].t=dis;e[num].pre=head[from];head[from]=num; } void spfa() {for (int i=1;i<=T;i++) dis[i]=0x7fffff;team[++Tail]=Ts;f[Ts]=1;dis[Ts]=0;while (Head<=Tail){int ki=team[++Head];f[ki]=0;for (int i=head[ki];i;i=e[i].pre){int vi=e[i].v;if (dis[vi]>dis[ki]+e[i].t){dis[vi]=dis[ki]+e[i].t;if (!f[vi]){team[++Tail]=vi;f[vi]=1;}} }} } int main() {scanf("%d%d%d%d",&T,&C,&Ts,&Te); for (int i=1,Rs,Re,Ci;i<=C;i++){scanf("%d%d%d",&Rs,&Re,&Ci);add(Rs,Re,Ci);add(Re,Rs,Ci);}spfa();printf("%d\n",dis[Te]); } spfa

?

?

轉載于:https://www.cnblogs.com/sjymj/p/6054349.html

總結

以上是生活随笔為你收集整理的codevs 1557 热浪的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。