hdu 1874 最短路径

#include <cstdio> #include <map> #include <string> #include <iostream> using namespace std; const int INF=0x3f3f3f3f,N=207; int w[N][N],vis[N],dis[N]; int main() { int n,m,s,d; while(~scanf("%d%d",&n,&m)) { for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(i==j) w[i][j]=0; else w[i][j]=INF; for(int i=0;i<m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); if(w[a][b]>c) w[a][b]=w[b][a]=c;//考虑一条路的多种情况 } scanf("%d%d",&s,&d); for(int i=0;i<n;i++) { vis[i]=0; dis[i]=w[s][i];//若路径不存在dis[i]为INF } vis[s]=1; dis[s]=0; while(1) { int p=-1; int mi=INF; for(int i=0;i<n;i++) if(mi>dis[i]&&!vis[i])//未被标记的才可录入 mi=dis[p=i]; if(p==-1) break; vis[p]=1; for(int i=0;i<n;i++) if(dis[i]>(dis[p]+w[p][i])&&(!vis[i])) dis[i]=dis[p]+w[p][i]; } if(dis[d]!=INF) printf("%d\n",dis[d]); else printf("-1\n"); } }