你看这数据范围,是不是想到了一点偷懒的算法?
没错就是 n^3的 floyd
#include<bits/stdc++.h>
using namespace std;
int f[105][105];
int n,m,a,b,c;
int main()
{
memset(f,10,sizeof(f));
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>a>>b>>c;
f[a][b]=c;
f[b][a]=c;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
int ans=0;
for(int i=2;i<=n;i++)
ans=max(ans,f[1][i]);
if(ans==f[101][101])
cout<<"-1"<<endl;
else
cout<<ans<<endl;
return 0;
}