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

题目链接：

题目大意：

给出矩阵，矩阵中每个元素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 ;

 }

巴特西

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

最新文章

热门文章