POJ 1502 MPI Maelstrom 最短路

最短路模板。

題意：從‘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;
}