HDU 2544

#include <stdio.h> #include <iostream> #include <string.h> using namespace std; int Map[110][110]; int flag[110]; int dis[110]; int n,m; int x,y; int Min[2]; const int INF = 0x3f3f3f3f; void Dijkstra(int a) { int t; for(int j=1;j<=n;j++) { Min[0]=INF;Min[1]=0; for(int i=1;i<=n;i++) { if(!flag[i]&&dis[i]<Min[0]) { Min[0]=dis[i]; Min[1]=i; } } flag[Min[1]]=1; t=Min[1]; for(int i=1;i<=n;i++) { if(!flag[i]&&Map[i][t]+dis[t]<dis[i]) dis[i]=Map[i][t]+dis[t]; //开始我这里是if(!flag[i]&&Map[i][t]+Map[t][1]<dis[i]) dis[i]=Map[i][t]+Map[t][1] //这里我找了很长时间才发现 } } } int main() { while((scanf("%d%d",&n,&m)!=EOF),n+m) { memset(Map,INF,sizeof(Map)); memset(flag,0,sizeof(flag)); memset(dis,INF-1,sizeof(dis)); for(int i=1;i<=m;i++) { cin>>x>>y; cin>>Map[x][y]; //这里先前用cin>>x>>y>>Map[x][y],结果Map[x][y]根本就没被初始化 Map[y][x]=Map[x][y]; } for(int i=1;i<=n;i++) dis[i]=Map[i][1]; flag[1]=1; Dijkstra(1); cout<<dis[n]<<endl; } return 0; }