题意：一共有N个地点，分别编号为1-N，这N个地点之间互相有一些道路连通，两个地点之间可能有多条道路连通，但是并不存在一条两端都是同一个地点的道路。算出至少要走的路程。
#include <cstdio> #include <map> #include <string> #include <iostream> using namespace std; const int INF=0x3f3f3f3f,N=1007; int w[N][N],vis[N],dis[N]; int main() { int n,m,s,d; scanf("%d%d%d%d",&n,&m,&s,&d); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(i==j) w[i][j]=0; else w[i][j]=INF; //没有的路径标记为INF } for(int i=0;i<m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); if(c<w[a][b]) w[a][b]=w[b][a]=c; } for(int i=1;i<=n;i++)//先将所有点到起点的路程记录下来 { vis[i]=0; dis[i]=w[s][i]; } vis[s]=1;//起点不可再计算在内 dis[s]=0;//起点到起点距离为0 while(1) { int mi=0x3f3f3f3f,p=-1; for(int i=1;i<=n;i++) if(!vis[i]) if(mi>dis[i]) { mi=dis[i]; p=i; } //记录下路程最短的点 if(p==-1) break; //如果没有路可以遍历那就结束 vis[p]=1; //已经走过的点不能再走 for(int i=1;i<=n;i++) if(!vis[i]&&dis[i]>(dis[p]+w[p][i]))//记录下起点到某点最短的路径并且走过的点不可再走 dis[i]=dis[p]+w[p][i]; } printf("%d\n",dis[d]);//输出题目要求输出的点 }