【hdu 2544】 最短路 （dijkstra 写的第一个最短路，也是dijkstra算法，纪念一下）
最短路 Time Limit : 5000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)Total Submission(s) : 11 Accepted Submission(s) : 8Problem DescriptionInputOutputSample InputSample Output#include<cstdio>#include<cstring>#define INF 0x7ffffff#define MEM(arr,k) memset(arr,k,sizeof(arr))int map[105][105];int dis[105];//记录从第一个点（s） 到其他点的最短距离bool visit[105];//标记该点是否被选中（加入到集合S）int Dijkstra(int s,int n){ int i,j; MEM(visit,false); for(i=1;i<=n;i++) dis[i]=map[s][i]; dis[s]=0;//初始时，只有s点被选中 visit[s]=true; for(i=1;i<=n;i++) { int tmp=INF; int k; for(j=1;j<=n;j++) if(!visit[j]&&dis[j]<tmp) tmp=dis[k=j];//选中“一个”从s出发的最短的点（每次都从更新后的点中选出最短的且未被纳入集合S的点 if(tmp==INF) break; visit[k]=true; for(j=1;j<=n;j++) { if(!visit[j]&&dis[j]>dis[k]+map[k][j])//松弛操作，原理：三角形第三边大于其他两边之和 dis[j]=dis[k]+map[k][j]; //更新所有的从k出发的dis } } return dis[n]; }int main(){ int n,m,i,j,a,b,c; while(scanf("%d%d",&n,&m),(n||m)) { //MEM(map,INF); 注意memset只能初始化为0或者-1，不能初始化为其他数！！！ for(i=1;i<=n;i++) for(j=1;j<=n;j++) map[i][j]=INF; for(i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); map[a][b]=map[b][a]=c; } printf("%d\n",Dijkstra(1,n)); } return 0;}
