poj1122 - FDNY to the Rescue!

                            想看更多的解题报告:http://blog.csdn.net/wangjian8006/article/details/7870410
                              转载请注明出处：http://blog.csdn.net/wangjian8006

题目大意：在一个地图上,找出从消防站到着火点的最短时间与最短时间中所走的点
只有一组数据
第一行代表一张地图,有n个点
接着是一个n×n的矩阵,代表从第i行j列中,i到j的时间,-1代表不能到达
最后一行,第一个数代表着火点,后面多个数代表消防站
输出的是消防站  着火点 时间 路径

解题思路：一个变形的最短路，将所有边反过来从着火点求一次最短路径，就可以求出从所有点到
着火点的最短路径，在算最短路径的时候记录路径点，这样从时间小的输出即可

/*
Memory 176K
Time   0MS
*/
#include<iostream>
using namespace std;
#define MAXV 20
#define INF INT_MAX

int map[MAXV][MAXV],d[MAXV],parent[MAXV];
int n,fire,stasum,station[MAXV];

void dijkstra(){
	int i,j,v,tmp;
	bool vis[MAXV];
	memset(parent,-1,sizeof(parent));
	memset(vis,false,sizeof(vis));
	for(i=1;i<=n;i++) d[i]=INF;
	d[fire]=0;

	for(i=1;i<=n;i++){
		tmp=INF;
		for(j=1;j<=n;j++)
			if(d[j]<tmp && !vis[j]){
				tmp=d[j];
				v=j;
			}
		vis[v]=true;
		for(j=1;j<=n;j++){
			if(!vis[j] && map[v][j]!=-1 && d[j]>d[v]+map[v][j]){		//-1不能走
				d[j]=d[v]+map[v][j];
				parent[j]=v;		//记录路径
			}
		}
	}
}

void output(){
	int j,i,tmp,v;
	printf("Org	Dest	Time	Path\n");
	
	j=0;
	while(j!=stasum){
		tmp=INF;
		for(i=1;i<=n;i++){					//每次找最小的时间输出
			if(station[i] && d[i]<tmp){
				tmp=d[i];
				v=i;
			}
		}
		station[v]=0;						//将这个站点设为非消防站
		printf("%d	%d	%d",v,fire,d[v]);
		while(v!=-1){
			printf("	%d",v);
			v=parent[v];
		}
		printf("\n");
		j++;
	}
}

int main(){
	int i,j,x;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			scanf("%d",&map[j][i]);		//边反向存储
		}
	}
	scanf("%d",&fire);
	stasum=0;
	memset(station,0,sizeof(station));
	while(~scanf("%d",&x)) {
		station[x]=1;					//标记消防站
		stasum++;						//计算消防站总数
	}

	dijkstra();
	output();
	return 0;
}