这道题有坑，两城市之间可能有多路径，在最初录入路径的时候选择权值最小的那条。
迪杰斯特拉算法：
#include<stdio.h>
#include<string.h>
const int maxint = 200000000;
bool s[210];
int path[210];
int d[210];
int arcs[210][210];
int S,T,M,N;
int shortestpath_dij(int v0,int vi)
{int n=N;int i,v,w;for(v=0; v<n; v++){s[v]=false;d[v]=arcs[v0][v];if(d[v]<maxint)path[v]=v0;else path[v]=-1;}s[v0]=true;d[v0]=0;for(i=1; i<n; ++i){int min0=maxint;for(w=0; w<n; w++){if(!s[w] && d[w]<min0){v=w;min0=d[w];}}s[v]=true;for(w=0; w<n; w++)if(!s[w] && (d[v]+arcs[v][w]<d[w])){d[w]=d[v]+arcs[v][w];path[w]=v;}}return d[vi];
}
int main()
{int a,b,lenth;while(scanf("%d %d",&N,&M)!=EOF){for(int i=0; i<N; i++)for(int j=0; j<N; j++)arcs[i][j]=maxint;for(int i=0; i<M; i++){scanf("%d %d %d",&a,&b,&lenth);if(lenth<arcs[a][b])arcs[a][b]=arcs[b][a]=lenth;}scanf("%d %d",&S,&T);int ans=shortestpath_dij(S,T);if(s[T]==true)printf("%d\n",ans);else printf("-1\n");}return 0;
}
弗洛伊德算法：
#include<stdio.h>
#include<string.h>
const int maxint = 0x3f3f3f;
int path[210][210];
int d[210][210];
int S,T,M,N;
int shortestpath_floyed(int v0,int vi)
{int n=N;for(int i=0; i<n; i++)for(int j=0; j<n; j++){if(d[i][j]<maxint)path[i][j]=i;else path[i][j]=-1;}for(int k=0; k<n; k++)for(int i=0; i<n; i++)for(int j=0; j<n; j++)if(d[i][k]+d[k][j]<d[i][j]){d[i][j]=d[i][k]+d[k][j];path[i][j]=path[k][j];}return d[v0][vi];
}
int main()
{int a,b,lenth;while(scanf("%d %d",&N,&M)!=EOF){for(int i=0; i<N; i++)for(int j=0; j<N; j++)if(i==j)d[i][j]==0;elsed[i][j]=maxint;for(int i=0; i<M; i++){scanf("%d %d %d",&a,&b,&lenth);if(lenth<d[a][b])d[a][b]=d[b][a]=lenth;}scanf("%d %d",&S,&T);int ans=shortestpath_floyed(S,T);if(ans>=0 && ans<maxint)printf("%d\n",ans);else printf("-1\n");}return 0;
}