POJ 1122 FDNY to the Rescue!（最短路+路径输出）

题意：
给出地图并且给出终点和多个起点，输出从各个起点到终点的路径和时间。

思路：

因为有多个起点，所以这里反向建图，这样就相当于把终点变成了起点，然后跑一遍最短路即可。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<sstream>
  6 #include<vector>
  7 #include<stack>
  8 #include<queue>
  9 #include<cmath>
 10 #include<map>
 11 #include<set>
 12 using namespace std;
 13 typedef long long ll;
 14 typedef long long ull;
 15 typedef pair<int,int> pll;
 16 const int INF = 0x3f3f3f3f;
 17 const int maxn = 500 + 5;
 18 
 19 int n;
 20 int mp[25][25];
 21 
 22 int vis[25];
 23 int d[25],path[25];
 24 int src, dst[25];
 25 
 26 struct node
 27 {
 28     int dst;
 29     int time;
 30 }tar[25];
 31 
 32 bool cmp(node a,node b)
 33 {
 34     return a.time<b.time;
 35 }
 36 
 37 void dijkstra(int src)
 38 {
 39     memset(vis,0,sizeof(vis));
 40     d[src]=0;
 41 
 42     for(int i=1;i<=n;i++)
 43     {
 44         int MIN=INF;
 45         int pos;
 46         for(int j=1;j<=n;j++)
 47         {
 48             if(!vis[j] && d[j]<MIN)
 49             {
 50                 MIN=d[j];
 51                 pos=j;
 52             }
 53         }
 54 
 55         if(MIN==INF)  break;
 56         vis[pos]=1;
 57 
 58         for(int j=1;j<=n;j++)
 59         {
 60             if(!vis[j] && mp[pos][j]+d[pos]<d[j])
 61             {
 62                 d[j]=mp[pos][j]+d[pos];
 63                 path[j]=pos;
 64             }
 65         }
 66     }
 67 }
 68 
 69 void print_path(int i)
 70 {
 71     if(i==-1)  return;
 72     printf("	%d",i);
 73     print_path(path[i]);
 74 }
 75 
 76 int main()
 77 {
 78     //freopen("in.txt","r",stdin);
 79     while(~scanf("%d",&n))
 80     {
 81         memset(path,-1,sizeof(path));
 82         memset(d,INF,sizeof(d));
 83 
 84         for(int i=1;i<=n;i++)
 85             for(int j=1;j<=n;j++)
 86             {
 87                scanf("%d",&mp[j][i]);
 88                if(mp[j][i]==-1)  mp[j][i]=INF;
 89             }
 90 
 91         scanf("%d",&src);
 92         int cnt=0; char c;
 93         while(scanf("%d%c",&tar[cnt++].dst,&c) && c!='
');
 94 
 95         dijkstra(src);
 96         printf("Org""	""Dest""	""Time""	""Path
");
 97 
 98         for(int i=0;i<cnt;i++)
 99             tar[i].time=d[tar[i].dst];
100 
101         sort(tar,tar+cnt,cmp);
102         for(int i=0;i<cnt;i++)
103         {
104             printf("%d	%d	%d",tar[i].dst,src,tar[i].time);
105             print_path(tar[i].dst);
106             printf("
");
107         }
108         printf("
");
109     }
110     return 0;
111 }