大家好，又见面了，我是你们的朋友全栈君。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=405;
const int inf=4000005;
int d1[maxn][maxn],n,m,g[maxn][maxn],d2[maxn][maxn],d3[maxn][maxn];//d1最短路径,d2最大边最小,d3最小边最大。
void init()
{
scanf("%d%d%d",&n,&m);
for(int i=1;i<=n;i++)//初值
for(int j=1;j<=n;j++)
{
if(i==j) g[i][j]=0;
else g[i][j]=inf;
}
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
g[x][y]=z;
g[y][x]=z;
}
}
void floyd()
{
memcpy(d1,g,sizeof(d1));
memcpy(d2,g,sizeof(d2));
memcpy(d3,g,sizeof(d3));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(d2[i][j]==inf)
d2[i][j]=-inf;
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(d1[i][k]+d1[k][j]<d1[i][j])
d1[i][j]=d1[i][k]+d1[k][j];
int x=min(d2[i][k],d2[k][j]);
d2[i][j]=max(d2[i][j],x);
int t=max(d3[i][k],d3[k][j]);
d3[i][j]=min(d3[i][j],t);
}
}
int main()
{
init();
floyd();
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/147719.html原文链接：https://javaforall.net
