最短路模板。

題意：從‘1’點發出一個信號到各個點，不同的點可以同時發出一個信號但到達目標的時間不同，問所有點接受到信號所耗費的最短時間為多少。

思路：迪杰斯特拉求出1點到各個點的最短路，遍歷一遍找到其中的最大值就可以了。

#include<stdio.h> #include<string.h> #include<cstring> #include<string> #include<math.h> #include<queue> #include<algorithm> #include<iostream> #include<stdlib.h> #include<cmath>#define INF 0x3f3f3f3f #define MAX 1005using namespace std;int Map[MAX][MAX],n,vis[MAX],dist[MAX];void Add(char str[],int x,int y) {int i,len=strlen(str),num=0;if(str[0]=='x'){Map[x][y]=Map[y][x]=INF;}else{for(i=0;i<len;i++){num=num*10+(str[i]-'0');}Map[x][y]=Map[y][x]=num;} }int dij() {int i,j,k,minn;memset(vis,0,sizeof(vis));for(i=2;i<=n;i++)dist[i]=Map[1][i];vis[1]=1;for(i=1;i<n;i++){minn=INF;for(j=1;j<=n;j++){if(minn > dist[j] && !vis[j]){minn=dist[j];k=j;}}vis[k]=1;for(j=1;j<=n;j++){if(dist[j] > dist[k] + Map[k][j])dist[j]=dist[k]+Map[k][j];}}int ans=0;for(i=2;i<=n;i++)ans=max(dist[i],ans); //遍歷找到最大邊return ans; }int main() {int i,j;char str[MAX];while(scanf("%d",&n)!=EOF){for(i=2;i<=n;i++){for(j=1;j<i;j++){scanf("%s",str);Add(str,i,j);}}int ans=dij();printf("%d\n",ans);}return 0; }

　　

轉載于:https://www.cnblogs.com/alan-W/p/5665622.html

總結

以上是生活随笔為你收集整理的POJ 1502MPI Maelstrom 最短路的全部內容，希望文章能夠幫你解決所遇到的問題。

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