小于400直接跑floyd
因为要找最小的 所以我们需要遍历1 到i~n
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int dist[N][N];
int n,m;
int main()
{
cin>>n>>m;
memset(dist,0x3f,sizeof dist);
while(m -- )
{
int a,b,c;
cin>>a>>b>>c;
if(a == b )
dist[a][b] = dist[b][a] = 0;
else
dist[a][b] = dist[b][a] = min(dist[a][b],c);
}
for(int k1=1;k1<=n;k1++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dist[i][j] = min(dist[i][j],dist[i][k1]+dist[k1][j]);
}
}
}
if(dist[1][n] == 0x3f3f3f3f)
cout<<-1<<endl;
else
{
int maxx = 0;
for(int i=1;i<=n;i++)
maxx = max(maxx,dist[1][i]);
cout<<maxx;
}
return 0;
}