POJ1122 记录前驱树Dij
#include<stdio.h>#include<stdlib.h>#include<algorithm>#include <iostream>using namespace std;const int MAX=25;const int INF=1<<27;//graph info.int n;int w[MAX][MAX];//dij info.int s;int dist[MAX];int p[MAX];bool flag[MAX];int dest[MAX];//消防站所在顶点void reversal(){int i,j;for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(w[i][j]==-1) w[i][j]=INF;}}for(i=1;i<=n;i++){for(j=1;j<i;j++){w[i][j]^=w[j][i]^=w[i][j]^=w[j][i];}}}void dij(){int i;for(i=1;i<=n;i++){//注：这里最好不要初始化为INF和i/-1，否则出错或者不好写，待总结dist[i]=w[s][i]; p[i]=s;}memset(flag,false,sizeof(flag));flag[s]=true;int time=n-1;while(time--){//找本次加入S的点curint cur;int minValue=INF;for(i=1;i<=n;i++){if(flag[i]==false && dist[i]<minValue){minValue=dist[i];cur=i;}}flag[cur]=true;//更新cur的邻接点for(i=1;i<=n;i++){if(flag[i]==false && w[cur][i]<INF && dist[cur]+w[cur][i]<dist[i]){p[i]=cur;dist[i]=dist[cur]+w[cur][i];}}}}//s: 目的点void printPath(int i){printf("%d\t",i);if(i!=s)printPath(p[i]);}//dest[i]中节点按照dist[dest[i]]升序排列bool compare(int a,int b){return dist[a]<dist[b];}int main(){//输入scanf("%d",&n);int i,j;int tempInt=-1;for(i=1;i<=n;i++){for(j=1;j<=n;j++){scanf("%d",&w[i][j]);}}scanf("%d",&s);int pos=1;while(scanf("%d",&dest[pos])){ //???通用方式pos++;char ch=getchar();if(ch=='\n')break;}pos--;//dijreversal();dij();//输出printf("%s\t%s\t%s\t%s\n","Org","Dest","Time","Path");sort(dest+1,dest+pos+1,compare);for(i=1;i<=pos;i++){printf("%d\t%d\t",dest[i],s);printf("%d\t",dist[dest[i]]);printPath(dest[i]);printf("\n");}system("pause");return 0;}?