传送门 floyd的模板题。。。
#include<bits/stdc++.h> using namespace std; int n,m; const int N=200; int dp[N][N]; int main(){ while(scanf("%d%d",&n,&m),n+m){ memset(dp,0x3f3f,sizeof(dp)); for(int i=1;i<=m;i++){ int a,b,l; scanf("%d%d%d",&a,&b,&l); dp[a][b]=l; dp[b][a]=l; } for(int i=1;i<=n;i++) dp[i][i]=0; for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[i][j]=min(dp[i][k]+dp[k][j],dp[i][j]); printf("%d\n",dp[1][n]); } }