1557 熱浪

?

?時間限制: 1 s ?空間限制: 256000 KB ?題目等級 : 鉆石 Diamond? 題目描述?Description

德克薩斯純樸的民眾們這個夏天正在遭受巨大的熱浪！！！他們的德克薩斯長角牛吃起來不錯，可是他們并不是很擅長生產(chǎn)富含奶油的乳製品。Farmer?John此時以先天下之憂而憂，后天下之樂而樂的精神，身先士卒地承擔(dān)起向德克薩斯運送大量的營養(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)最小的總費用。

輸入描述?Input Description

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

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

輸出描述?Output Description

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

樣例輸入?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

數(shù)據(jù)范圍及提示?Data Size & Hint

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

SPFA寫法

#include<cstdio> #include<iostream> #include<cstring> using namespace std; int d[100010],u[100010],v[100100],head[100010],next[100010],q[100010],f[100010]; int n,m,S,T,x,y,z,tot=0; void bianbao(int x,int y,int z){u[++tot]=y;v[tot]=z;next[tot]=head[x];head[x]=tot; } void spfa(){memset(d,127,sizeof(d));d[S]=0;int h=0,t=1;q[1]=S;f[S]=1;while(h<t){int p=q[++h];f[p]=0;for(int i=head[p];i;i=next[i])if(d[u[i]]>d[p]+v[i]){d[u[i]]=d[p]+v[i];if(!f[u[i]]){f[u[i]]=1;q[++t]=u[i];}}}printf("%d\n",d[T]); } int main() {scanf("%d%d%d%d",&n,&m,&S,&T);for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);bianbao(x,y,z);bianbao(y,x,z);}spfa();return 0; }

?

djc矩陣寫法

#include<iostream> #include<cstdio> #include<cstring> #define INF 10000010 #define N 5101 using namespace std; int n,g[N][N],dis[N]; bool vis[N]; void djc(int u){memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++) dis[i]=g[u][i];dis[u]=0;vis[u]=1;for(int i=2;i<=n;i++){int m=INF;for(int j=1;j<=n;j++)if(!vis[j]&&dis[j]<m){u=j;m=dis[j];}vis[u]=1;for(int j=1;j<=n;j++) dis[j]=min(dis[j],dis[u]+g[u][j]);} } int main() {int m,u,v,x,y,z;scanf("%d%d%d%d",&n,&m,&u,&v);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)g[i][j]=INF;for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);g[x][y]=min(g[x][y],z);g[y][x]=min(g[y][x],z);}djc(u);printf("%d\n",dis[v]);return 0; }

?

djc編表寫法

#include<cstdio> #include<cstring> #include<iostream> using namespace std; #define INF 10000000 #define maxn 3000010 int qd;//到那個點的距離 int dis[maxn]; int vis[maxn]; int n,m,q,head[maxn]; struct node{int u,v,w,next; }e[maxn]; void add(int u,int v,int w,int i){e[i].u=u;if(u==qd) dis[v]=w;e[i].v=v;e[i].w=w;e[i].next=head[u];head[u]=i; } void djc(int u){dis[u]=0;vis[u]=1;for(int i=2;i<=n;i++){int m=INF;for(int j=1;j<=n;j++){if(!vis[j]&&dis[j]<m){u=j;m=dis[j];} }//if(u==qd) break; vis[u]=1;for(int l=head[u];l;l=e[l].next){if(dis[e[l].v]>dis[e[l].u]+e[l].w){dis[e[l].v]=dis[e[l].u]+e[l].w;}}} } int main() {int m,u,v,x,y,z;memset(dis,127,sizeof dis);scanf("%d%d%d%d",&n,&m,&qd,&v);for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);add(x,y,z,i);add(y,x,z,i+m);}djc(qd);printf("%d\n",dis[v]);return 0; }

?

floyed~沒寫啊~太水了~

?

轉(zhuǎn)載于:https://www.cnblogs.com/shenben/p/5471531.html

總結(jié)

以上是生活随笔為你收集整理的最短路算法整理 1557 热浪的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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