Invitation Cards POJ - 1511

题目链接：https://vjudge.net/problem/POJ-1511

思路：题目意思就是，从1出发到所有城市，再从所有城市回到1的最短时间。

那么我们只要正跑一次图，然后反向存边，再跑一次图，把所有单源最短路相加就是答案了。

emmm,这题，很卡时间，作为一个懒人，用c++的输入输出，加了简单的快读，用了链式前项星，

还是险些通过，感觉遇到很大的输入数据，用c++时，最好减少空间申请和回收的开销，不然会卡。

我一个优先队列在函数申请用，T了，在全局申请，再清空就A了。。。当然，这是之前的，后面改了下，

emm，7780ms。。。当然，这题用dijkstra一定要堆优化一下，点有1e6之多。。。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <queue>
  6 #include <string>
  7 #include <map>
  8 #include <cmath>
  9 #include <iomanip>
 10 using namespace std;
 11  
 12 typedef long long LL;
 13 #define inf 1e10
 14 #define rep(i,j,k) for(int i = (j); i <= (k); i++)
 15 #define rep__(i,j,k) for(int i = (j); i < (k); i++)
 16 #define per(i,j,k) for(int i = (j); i >= (k); i--)
 17 #define per__(i,j,k) for(int i = (j); i > (k); i--)
 18 
 19 const int N = 1e6 + 10;
 20 int head[N];
 21 int vis[N];
 22 int dis[N];
 23 int U[N],V[N],W[N];
 24 int cnt;
 25 LL ans;
 26 
 27 int n,m;
 28 
 29 struct Edge{
 30     int to;
 31     int w;
 32     int next;
 33 }e[N];
 34 
 35 struct node{
 36     int loc;
 37     int w;
 38 
 39     bool friend operator< (const node& a,const node& b){
 40         return a.w > b.w;
 41     }
 42 };
 43 priority_queue<node > que;
 44 
 45 void add(int u,int v,int w){
 46     e[cnt].to = v;
 47     e[cnt].w = w;
 48     e[cnt].next = head[u];
 49     head[u] = cnt++;
 50 }
 51 
 52 void dijkstra(){
 53 
 54     while(!que.empty()) que.pop();
 55     rep(i,1,n) vis[i] = false;
 56     rep(i,1,n) dis[i] = inf;
 57     dis[1] = 0;
 58     que.push(node{1,0});
 59 
 60     while(!que.empty()){
 61         int u = que.top().loc;
 62         que.pop();
 63         if(vis[u]) continue;
 64         vis[u] = true;
 65 
 66         for(int o = head[u]; ~o; o = e[o].next){
 67             int v = e[o].to;
 68             int w = e[o].w;
 69 
 70             if(!vis[v] && dis[v] > dis[u] + w){
 71                 dis[v] = dis[u] + w;
 72                 que.push(node{v,dis[v]});
 73             }
 74         }
 75     }
 76     rep(i,1,n) ans += dis[i];
 77 }
 78 
 79 int main(){
 80 
 81     ios::sync_with_stdio(false);
 82     cin.tie(0);
 83 
 84     int T;
 85     cin >> T;
 86     while(T--){
 87         cin >> n >> m;
 88 
 89         rep(i,1,n) head[i] = -1;
 90         cnt = 0;
 91 
 92         int u,v,w;
 93         rep(i,1,m){
 94             cin >> U[i] >> V[i] >> W[i];
 95             add(U[i],V[i],W[i]); //正向存边
 96         }
 97 
 98         ans = 0;
 99         dijkstra();  
100 
101         rep(i,1,n) head[i] = -1;
102         cnt = 0;
103         rep(i,1,m){
104             add(V[i],U[i],W[i]); //反向存边
105         }
106 
107         dijkstra();
108         cout << ans << endl;
109     }
110 
111     getchar(); getchar();
112     return 0;
113 }