题目链接：poj1122 FDNY to the Rescue!
题意：给出矩阵，矩阵中每个元素tij表示从第i个交叉路口到第j个交叉路口所需时间，若tij为-1则表示两交叉路口之间没有直接路径，再给出火警位置所在的交叉路口 和 一个或多个消防站所处的交叉路口位置。输出要求按消防站到火警位置所需时间从小到大排列，输出信息包括消防站位置（初始位置），火警位置（目标位置），所需时间，最短路径上每个交叉路口。
题解：反向建图，从火警位置求一次最短路，求最短路时记录路径，按时间从小到大输出。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define CLR(a,b) memset((a),(b),sizeof((a)))
using namespace std; const int inf = 0x3f3f3f3f;
const int N = ;
int n, fire;
int g[N][N];//邻接矩阵存图
int s[N], d[N];
int path[N];//表示v0到vi最短路径顶点vi的前一个顶点序号
int shortest[N];//存储最短路径上的各个顶点序号
struct node{
int u, v, t;
}a[N];
int cmp(node a, node b){
return a.t < b.t;
}
void dij(){
int i, j, k;
CLR(s, );
for(i = ; i <= n; ++i){
d[i] = g[fire][i];
if(i != fire)
path[i] = fire;
else
path[i] = -;
}
s[fire] = ;
d[fire] = ;
for(i = ; i < n-; ++i){
int mi = inf, u = ;
for(j = ; j <= n ; ++j){
if(!s[j] && d[j] < mi){
u = j; mi = d[j];
}
}
s[u] = ;
for(k = ; k <= n; ++k){
if(!s[k] && d[u] + g[u][k] < d[k]){
d[k] = d[u] + g[u][k];
path[k] = u;
}
}
}
}
int main(){
int i, j, x, cnt;
scanf("%d", &n);
for(i = ; i <= n; ++i){//边反向存储
for(j = ; j <= n; ++j){
scanf("%d", &x);
if(x == -)
g[j][i] = inf;
else
g[j][i] = x;
}
}
scanf("%d", &fire);
dij();
cnt = ;
while(scanf("%d", &x) == ){
a[cnt].u = x;
a[cnt].v = fire;
a[cnt++].t = d[x];
}
sort(a, a+cnt, cmp);
printf("Org\tDest\tTime\tPath\n");
for(i = ; i < cnt; ++i){
printf("%d\t%d\t%d", a[i].u, a[i].v, a[i].t);
CLR(shortest, );
int k = ;//表示shortest数组中最后一个元素的下标
shortest[k] = a[i].u;
while(path[shortest[k]] != -){
k++;
shortest[k] = path[shortest[k-]];
}
for(j = ; j <= k; ++j) //倒向追踪，但是反向建图，因此正向输出
printf("\t%d", shortest[j]);
puts("");
}
return ;
}