【最短】信使
761 ワード
原題リンク
データは非常に小さく、Floydが使えます.Floydでノード1からすべてのノードへの最短ルートを求め,答えはこれらの最短ルートの中で最も長いものである.
コード実装:
データは非常に小さく、Floydが使えます.Floydでノード1からすべてのノードへの最短ルートを求め,答えはこれらの最短ルートの中で最も長いものである.
コード実装:
#include
#define N 100+10
using namespace std;
int d[N][N];
int n,m;
int main(){
cin>>n>>m;
memset(d,0x3f,sizeof d);
for(int i=1;i<=n;i++)d[i][i]=0;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
d[a][b]=min(d[a][b],c);
d[b][a]=d[a][b];
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
int ans=-1;
for(int i=1;i<=n;i++)
ans=max(ans,d[1][i]);
if(ans>=0x3f3f3f3f/2)cout<