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的点cur
		int 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--;

	//dij
	reversal();
	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;
}