https://vjudge.net/problem/17632/origin floyd 解法
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> using namespace std; int N,M; const int maxn=1e3+5; const int inf=0x3f3f3f3f; int a[maxn][maxn]; void floyd(){ for(int k=0;k<N;k++){ for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ a[i][j]=min(a[i][k]+a[k][j],a[i][j]); } } } } int main(){ int s,t,v; while(scanf("%d%d",&N,&M)!=EOF){ for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ if(i==j)a[i][j]=0; else a[i][j]=inf; } } int S,T; for(int i=0;i<M;i++){ scanf("%d%d%d",&s,&t,&v); a[s][t]=min(v,a[t][s]); a[t][s]=min(v,a[s][t]); } scanf("%d%d",&S,&T); floyd(); if(a[S][T]!=inf)printf("%d\n",a[S][T]); else printf("-1\n"); } return 0; }