zoj1053/poj1122-FDNY to the Rescue!

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=53

http://poj.org/problem?id=1122

总体来说，仍然是Dijkstra的模版题，但是还是有很大变通，又锻炼了思维，不至于思维现在就固化了；

而且需要特判；

题意为：输入case组数据（zoj有 , poj没有 ，然后再输入一个N，代表有N条路，然后就是N * N 的矩阵图，代表各段路之间的距离，当为-1时，代表此路不通；然后输出END代表末端（本来按照模版是起始点，但是由于后面还要输入多组数据作为起点），接着输入多组start;

需要求得就是最短路径和记录路径；

但是输出时有要求：

按照最短路径从小到大排序，然后分别输出起始点（即start点 ），终点（end),最短路，输出路径。

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std ;


const int INF = 1000000 ;
const int maxn = 20 ;
int n ;
int edge[ maxn ][ maxn ] ;
int S[ maxn ] ;
int dist[ maxn ] ;
int path[ maxn ] ;
int end;
 /*typedef struct Fire 
 {
   int street[MAX], len, start, E;
   bool operator < (const Fire &other) const 
   {
     return len < other.len;
   }
 }Fire;
 Fire fire[MAX];*/
 struct Fire
 {
		int street[ maxn] , len ,start , E ;
		bool operator < ( const Fire other )const 
		{
			return len < other.len ;
		}
}fire[ maxn ];

int cmp( const void  *x , const void  *y )
{
	return *(int *)x < *(int *)y ;
}
void Dijkstra( int v0 , Fire &su)
{
	int i , j , k ;
	for( i = 1 ; i <= n ; i++ )
	{
		dist[ i ] = edge[ v0 ][ i ] ;
		S[ i ] = 0 ; 
		if( i != v0 && dist[ i ] < INF )
			path[ i ] = v0 ;
		else
			path[ i ] =  -1 ;
	}
	S[ v0 ] = 1 ;
	dist[ v0 ] = 0 ;
	path[ v0 ] = -1 ;
	for( i = 1 ; i <= n - 1 ; i++ )
	{
		 int MIN = INF , u = v0 ;
		 for( j = 1 ; j <= n ; j++ )
		 {
				if( !S[ j ] && dist[ j ] < MIN )
				{
					u = j ; 
					MIN = dist[ j ] ;
				}
		}
		S[ u ] = 1 ;
		for( k = 1 ; k <= n ; k++ )
		{
			if( !S[ k ]&& edge[ u ][ k ] < INF && dist[ u ] + edge[ u ][ k ] < dist[ k ] )
			{
					dist[ k ] = dist[ u ] + edge[ u ][ k ] ;
					path[ k ] = u ;
			}
		}
		if( u == end)
			break;
	}
	k = 0 ;
	su.street[ k ] = end ;
	int ho = path[ end ] ;
	while( ho != -1 )
	{
		su.street[ ++k ] = ho;
		ho = path[ ho ] ;
	}
	su.E = k ;
	su.len =  dist[ end ] ;
}
/*	  k = 0; 
   su.street[k] = end; 
   int ho = path[end];
   while (ho != -1) 
   {
     su.street[++k] = ho; 
	 ho = path[ho];
   }
   su.E = k;
   su.len = dist[end];	
}*/
int main()
{
	int i , j  ;
	int Case ;
	scanf( "%d" , &Case );
	while( Case-- )
	{
		scanf( "%d" , &n ) ;
		memset( edge , 0 , sizeof( edge ) ) ;
		for( i = 1 ; i <= n ; i++ )
		{
			for( j = 1 ; j <= n ; j++ )
			{
				scanf( "%d" , &edge[ i ][ j ] ) ;
				if( edge[ i ][ j ] == -1 )
					edge[ i ][ j ] = INF ;
			}
		}
		scanf( "%d" , &end ) ;
		  printf("Org\tDest\tTime\tPath\n");
		int cnt = 0 , start ;
		while( ~scanf( "%d" , &start ) )
		{
			fire[ cnt ].start = start ;
			Dijkstra(start,fire[cnt]);
			cnt++ ; 
		}
		sort( fire ,fire + cnt ) ;
		for( i = 0  ; i < cnt ; i++ )
		{
			printf( "%d\t%d\t%d\t" , fire[ i ].start ,end , fire[ i ].len  ) ;
			for( j = fire[ i ].E ; j > 0 ; --j )
			{
				printf( "%d\t" , fire[ i ].street[ j ] ) ;
			}
			printf( "%d\n" , fire[ i ].street[ 0 ] ) ;
		}
	}
	return 0 ;
}