Description

Input

Output

Line 1: 
A label line with the headings for each column, exactly as shown in the example. 

Line 2 onwards (one line for each fire station): 
A sorted list (based on time) showing the fire station (origin), the destination site, time taken and a complete shortest path of nodes from the originating fire station to the fire location. 

Notes on output format: 
1. Columns are tab separated. 
2. If two or more firehouses are tied in time they can be printed in any order. 
3. If more than one path exists that has the same minimal time for a given location & firehouse, either one can be printed on the output. 
4. If the fire location and the fire station locations happen to be the same intersection, the output will indicate that the origin and destination have the same intersection number, the time will be "0" and the nodes in the shortest path will show just one number, the fire location. 
Next is the picture for the sample input data. 

Sample Input

6 
0  3  4 -1 -1 -1 
-1 0  4  5 -1 -1 
2  3  0 -1 -1  2 
8  9  5  0  1 -1 
7  2  1 -1  0 -1 
5 -1  4  5  4  0 
2  4  5  6 
In the above input the last line indicates that "2" is the location of the fire and "4", "5" and "6" are the intersections where fire stations are located. 

Sample Output

Org	Dest	Time	Path
5	2	2	5	2
4	2	3	4	5	2
6	2	6	6	5	2

Source

题意：求各个消防点到失火点的距离和到达该点的路径。

思路：dijkstra求最短路，因为失火点只有一个，故可以求失火点到消防局的最短路，读入反向边。

#include"stdio.h"
#include"string.h"
#include"queue"
#include"algorithm"
using namespace std;
#define N 25
#define inf 0x7fffffff
int mark[N],g[N][N];
int dis[N],pre[N],n;  //记录最短路，记录路线
struct node
{
    int id,d;  //记录消防局小标和距离
}a[N];
bool cmp(node a,node b)
{
    return a.d<b.d;
}
void dijkstra(int s)
{
    int i,min,u;
	memset(pre,-1,sizeof(pre));
    for(i=1;i<=n;i++)
    {
        pre[i]=s;
        dis[i]=g[s][i];
        mark[i]=0;
    }
    mark[s]=1;
    while(1)
    {
        min=inf;
        u=s;
        for(i=1;i<=n;i++)
        {
            if(min>dis[i]&&!mark[i])
            {
                min=dis[i];
                u=i;
            }
        }
        if(u==s)
            break;
        mark[u]=1;
        for(i=1;i<=n;i++)
        {
            if(!mark[i]&&g[u][i]<inf&&g[u][i]+dis[u]<dis[i])
            {
                dis[i]=g[u][i]+dis[u];
                pre[i]=u;
            }
        }
    }
}
void work(int k)
{
    int i,j;
    a[0].d=-1;
    for(i=1;i<k;i++)
    {
        a[i].d=dis[a[i].id];
    }
    sort(a,a+k,cmp);
    printf("Org	Dest	Time	Path\n");
    for(i=1;i<k;i++)
    {
        printf("%d	%d	%d	%d	",a[i].id,a[0].id,a[i].d,a[i].id);
        for(j=pre[a[i].id];j!=a[0].id;j=pre[j])
        {
            printf("%d	",j);
        }
		if(a[i].id!=a[0].id)      //失火点和消防点相同
	        printf("%d\n",a[0].id);
		else
			printf("\n");
    }
}
int main()
{
    int i,j,t,k;
    char str[500];
    while(scanf("%d",&n)!=-1)
    {
        for(i=1;i<=n;i++) 
        {                  
            for(j=1;j<=n;j++)
            {
                scanf("%d",&g[j][i]);
                if(g[j][i]<0)   
                    g[j][i]=inf;
            }
        }
        gets(str);      
        gets(str);   
        t=k=0;
        for(i=0;str[i]!='\0';i++)
        {
            if(str[i]>='0'&&str[i]<='9')
            {
                t=t*10+str[i]-'0';
            }
            else if(t!=0)
            {
                a[k++].id=t;
                t=0;
            }
        }
		if(t!=0)      //末尾还有一个
			a[k++].id=t;
        memset(pre,-1,sizeof(pre));
        dijkstra(a[0].id);
        work(k);
    }
    return 0;
}