POJ-1511 Invitation Cards （单源最短路+逆向）

题目大意：

有向图，求从起点1到每个点的最短路然后再回到起点1的最短路之和。

解题分析：

在求每个点到1点的最短路径时，如果仅仅只是遍历每个点，对它们每一个都进行一次最短路算法，那么即使是用了堆优化的dijkstra，时间复杂度也高达$O(n^2log(n))$，而本题有1000000个点，毫无疑问，这种想法必然是不可行的，所以我们可以采用逆向思维，将图中的每一条有向边全部反向，然后以1为起点，仅做一次dijkstra,就能得到1到所有点的最短距离，即反向前的，所有点到1点的最短距离。所以，本题的正解应为：先以1为起点，做一次dijkstra,算出，1到所有点的最短距离，然后将边反向，再以1为起点，做一次dijkstra,此时就能得到，其他所有点到1的最短距离，将所有的最短距离相加，即为答案。时间复杂度为$O(nlogn)$。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <queue>
  4 #include <algorithm>
  5 #include <iostream>
  6 using namespace std;
  7 
  8 #define INF 0x3f3f3f3f
  9 const int maxn =1000000+100;
 10 
 11 int n,m;
 12 struct Edge{
 13     int to;
 14     int next;
 15     int w;
 16 };
 17 
 18 Edge edge[maxn],redge[maxn];
 19 
 20 struct NODE{
 21     int index;
 22     int dis;
 23     bool operator < (NODE const &tmp)const{
 24         return dis>tmp.dis;
 25     }
 26 }d[maxn];
 27 
 28 int dist[maxn];   
 29 int cnt,rcnt,head1[maxn],head2[maxn],vis[maxn];
 30 
 31 void init(){
 32     memset(head1,-1,sizeof(head1));
 33     memset(head2,-1,sizeof(head2));
 34     cnt=0,rcnt=0;
 35 }
 36 
 37 void add1(int u,int v,int w){
 38     edge[cnt].to=v;edge[cnt].w=w;
 39     edge[cnt].next=head1[u];
 40     head1[u]=cnt++;
 41 }
 42 
 43 void add2(int u,int v,int w){
 44     redge[rcnt].to=v;redge[rcnt].w=w;
 45     redge[rcnt].next=head2[u];
 46     head2[u]=rcnt++;
 47 }
 48 
 49 void dijkstra1(int st){           
 50     for(int i=1;i<=n;i++){
 51         vis[i]=0;d[i].dis=INF,d[i].index=i;
 52     }
 53 
 54     priority_queue<NODE>q;
 55     d[st].dis=0;q.push(d[st]);
 56     while(!q.empty()){
 57         int u=q.top().index;
 58         q.pop();
 59         if(vis[u])continue;
 60         vis[u]=1;
 61         for(int i=head1[u];i!=-1;i=edge[i].next){
 62             int v=edge[i].to;
 63             if(d[v].dis>d[u].dis+edge[i].w){
 64                 d[v].dis=d[u].dis+edge[i].w;
 65                 q.push(d[v]);
 66             }
 67         }
 68     }
 69 }
 70 
 71 void dijkstra2(int st){           //因为正、反向边的edge[],和head[]散组不同，所以要将另外再写一个dijkstra函数
 72     for(int i=1;i<=n;i++){
 73         vis[i]=0;d[i].dis=INF,d[i].index=i;
 74     }
 75 
 76     priority_queue<NODE>q;
 77     d[st].dis=0;q.push(d[st]);
 78     while(!q.empty()){
 79         int u=q.top().index;
 80         q.pop();
 81         if(vis[u])continue;
 82         vis[u]=1;
 83         for(int i=head2[u];i!=-1;i=redge[i].next){
 84             int v=redge[i].to;
 85             if(d[v].dis>d[u].dis+redge[i].w){
 86                 d[v].dis=d[u].dis+redge[i].w;
 87                 q.push(d[v]);
 88             }
 89         }
 90     }
 91 }
 92 
 93 int main(){
 94     int t;scanf("%d",&t);
 95     while(t--){
 96         scanf("%d %d",&n,&m);
 97         init();
 98         for(int i=1;i<=m;i++){
 99             int a,b,c;
100             scanf("%d %d %d",&a,&b,&c);
101             add1(a,b,c);          //存储该有向图正确的边
102             add2(b,a,c);          //将该有向图的所有边反向存储
103         }
104 
105         long long sum=0;
106 
107         dijkstra1(1);        //边未反向之前，求出1到所有点的最短路
108         for(int i=2;i<=n;i++){
109             sum+=d[i].dis;
110         }
111 
112         dijkstra2(1);       //将边反向后，求出所有点到1点的最短路
113         for(int i=2;i<=n;i++){
114             sum+=d[i].dis;
115         }
116         printf("%lld
",sum);
117     }
118     return 0;
119 }

2018-08-27