http://acm.hdu.edu.cn/showproblem.php?pid=2544
用dis[]存储源点到各点的距离，不能到达则为inf。 每次找到可以到达源点中最近的点，用这个点去更新dis[]，这里用到了贪心思想。每个点仅能更新一次，用vis来标记。因为一次更新后很多点的dis[]都可能发生变化，所以每次都需要从头开始找这个最近的点。
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int maxn=205; const int inf=0x3f3f3f3f; int map[maxn][maxn]; int dis[maxn]; int vis[maxn]; int main(){ int n,m,a,b,c; while(cin>>n>>m){ if(!n&&!m) break; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i==j) map[i][j]=0; else map[i][j]=inf; } } for(int i=0;i<m;i++){ cin>>a>>b>>c; map[a][b]=c; map[b][a]=c; } for(int i=1;i<=n;i++){ dis[i]=map[1][i]; } vis[1]=1; for(int i=1;i<=n-1;i++){ int min=inf,z; for(int j=1;j<=n;j++){ if(!vis[j]&&dis[j]<min){ min=dis[j]; z=j; } } vis[z]=1; for(int k=1;k<=n;k++){ if(map[z][k]<inf&&map[z][k]+dis[z]<dis[k]) dis[k]=map[z][k]+dis[z]; } } cout<<dis[n]<<endl; } }
