首页 > 代码库 > POJ 1502 MPI Maelstrom【floyd】
POJ 1502 MPI Maelstrom【floyd】
题目大意:求点1到所有点最短路径的最大值
思路:水题,单源最短路,网上解题清一色dijkstra,但是点数小于100显然floyd更简洁嘛
#include<cstdio>
#include<string.h>
#define maxn 101
#define inf 100000
using namespace std;
int read(){
int f=1,x=0;char ch=getchar();
while(ch<‘0‘||ch>‘9‘){if(ch==‘x‘)return inf;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}return x*f;
}
int n=read(),ans=0,a[maxn][maxn];
int main()
{
for(int i=1;i<=n-1;i++)
for(int j=1;j<=i;j++)a[i+1][j]=a[j][i+1]=read();
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)if(i!=k)
for(int j=1;j<=n;j++)if(j!=k&&j!=i&&a[i][k]+a[k][j]<a[i][j])a[i][j]=a[i][k]+a[k][j];
for(int i=2;i<=n;i++)if(a[1][i]>ans)ans=a[1][i];
printf("%d\n",ans);
return 0;
}
POJ 1502 MPI Maelstrom【floyd】