POJ-1122 FDNY to the Rescue!---Dijkstra+反向建图

题目链接：

https://vjudge.net/problem/POJ-1122

题目大意：

给出矩阵，矩阵中每个元素tij表示从第i个交叉路口到第j个交叉路口所需时间，若tij为-1则表示两交叉路口之间没有直接路径，再给出火警位置所在的交叉路口 和 一个或多个消防站所处的交叉路口位置。输出要求按消防站到火警位置所需时间从小到大排列，输出信息包括消防站位置（初始位置），火警位置（目标位置），所需时间，最短路径上每个交叉路口。

思路：

由于求的是其他点到某一点的最短路，所以反向建图，然后用dijkstra求出这点到其他点的最短路即可。求出来的就是其他点到这点的最短路，还需要保存路径。输入输出有格式要求，详细看代码

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<stack>

 #include<map>

 #include<set>

 #include<sstream>

 #define MEM(a, b) memset(a, b, sizeof(a));

 using namespace std;

 typedef long long ll;

 const int maxn =  + ;

 const int INF = 0x3f3f3f3f;

 int T, n, m, cases, tot;

 int Map[maxn][maxn], d[maxn], path[maxn];

 bool v[maxn];

 struct node

 {

     int id, time;

     bool operator < (const node& a)const

     {

         return time < a.time;

     }

 }a[maxn];

 void dijkstra(int u)

 {

     for(int i = ; i <= n; i++)d[i] = INF;

     d[u] = ;

     memset(path, -, sizeof(path));

     memset(v, , sizeof(v));

     for(int i = ; i < n; i++)

     {

         int x, m = INF;

         for(int i = ; i <= n; i++)if(!v[i] && m > d[i])m = d[x = i];

         v[x] = ;

         for(int i = ; i <= n; i++)

         {

             if(!v[i] && d[i] > d[x] + Map[x][i])

             {

                 d[i] = d[x] + Map[x][i];

                 path[i] = x;

             }

         }

     }

 }

 int main()

 {

     cin >> n;

     int tot = ;

     for(int i = ; i <= n; i++)

     {

         for(int j = ; j <= n; j++)

         {

             cin >> Map[i][j];

             if(Map[i][j] == -)Map[i][j] = INF;

         }

     }

     for(int i = ; i <= n; i++)

     {

         for(int j = i + ; j <= n; j++)swap(Map[i][j], Map[j][i]);

     }

     string s;

     int u, v;

     cin >> u;

     while(cin >> v)a[tot++].id = v;

     dijkstra(u);

     for(int i = ; i < tot; i++)

     {

         a[i].time = d[a[i].id];

     }

     sort(a, a + tot);

     printf("Org\tDest\tTime\tPath\n");

     for(int i = ; i < tot; i++)

     {

         printf("%d\t%d\t%d\t", a[i].id, u, a[i].time);

         int x = a[i].id;

         while(x != -)

         {

             printf("%d\t", x);

             x = path[x];

         }

         printf("\n");

     }

     return ;

 }