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

#include<iostream>
#include <cstdio>
#include <string.h>
#include<stdlib.h>
#define inf 1000000
using namespace std;
typedef struct fd{
	int org,dest,time,path[25];
}fd;
int cmp( const void *a , const void *b ) 
{ 
	struct fd *c = (fd *)a; 
	struct fd *d = (fd *)b; 
	return c->time - d->time;  
}
int main()
{
	int T,N,M,i,k,j,v0,u,temp;
	fd ff[25];
	int a[25][25],S[25],pre[25],min[25],shortest[25];
	cin>>T;
	while(T--)
	{
		cin>>N;
		for(i=1;i<=N;i++)
			for(j=1;j<=N;j++)
			{
				cin>>a[i][j];
				if(a[i][j]==-1) a[i][j]=inf;
			}
		int len=0;
		cin>>M;
		while(~scanf("%d",&v0))
		{
			ff[len].dest=M;
			ff[len].time=0;
			ff[len].org=v0;
			ff[len].path[v0]=-1;
			for(i=1;i<=N;i++)
			{
				S[i]=0;
				min[i]=a[v0][i];
				if(i!=v0&&min[i]<inf)  pre[i]=v0;
				else pre[i]=-1;
			}
			S[v0]=1;
			min[v0]=0;
			for(i=1;i<=N;i++)
			{
				u=v0,temp=inf;
				for(j=1;j<=N;j++)
				{
					if(!S[j]&&temp>min[j])
						u=j,temp=min[j];
				}
				S[u]=1;
				for(k=1;k<=N;k++)
				{
					if(!S[k]&&a[u][k]<inf&&min[k]>min[u]+a[u][k])
						pre[k]=u,min[k]=min[u]+a[u][k];
				}
			}
			ff[len].time=min[M];
			memset(shortest,0,sizeof(shortest));
			k=0;
			shortest[k]=M;
			while(pre[shortest[k]]!=-1)
			{
				k++;
				shortest[k]=pre[shortest[k-1]];
			}
			for(i=0;i<=k;i++)
				ff[len].path[i]=shortest[k-i];
			len++;
		}
		qsort(ff,len,sizeof(ff[0]),cmp);
		printf("Org     Dest    Time    Path\n");
		for(i=0;i<len;i++)
		{
			printf("%d\t%d\t%d\t",ff[i].org,ff[i].dest,ff[i].time);
			for(j=0;ff[i].path[j]!=M;j++)
				printf("%d\t",ff[i].path[j]);
			printf("%d\n",M);
		}
	}
	return 0;
}