Advertisement
trungore10

code_NOBITA

Nov 5th, 2019
150
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.06 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define int                     long long
  3. using namespace std;
  4.  
  5. void Read(int &val) {
  6.     val = 0; char c;
  7.     do { c = getchar(); } while (!isdigit(c));
  8.     while (isdigit(c)) { val = val * 10 + c - '0'; c = getchar(); }
  9. }
  10.  
  11. typedef pair<int, int> ii;
  12. struct dataHeap {
  13.     int u, type, val;
  14.     dataHeap() {}; dataHeap(int u, int type, int val) : u(u), type(type), val(val) {};
  15.     bool operator > (const dataHeap &a) const { return val > a.val; }
  16. };
  17. struct dataEdge {
  18.     int u, v, w;
  19.     dataEdge() {}; dataEdge(int u, int v, int w) : u(u), v(v), w(w) {};
  20.     bool operator < (const dataEdge &a) const { return w < a.w; }
  21. };
  22.  
  23. const int N = 1e5 + 4, oo = 1e17;
  24. int n, m, numDoor;
  25. vector<int> lisDoor;
  26. vector<ii> adj[N];
  27.  
  28. namespace Min_Distance_To_Tree {
  29.     int dist[N];
  30.     priority_queue<ii, vector<ii>, greater<ii> > heap;
  31.  
  32.     int Dijkstra() {
  33.         for (int i = 1; i <= n; ++i) dist[i] = oo; dist[1] = 0;
  34.         heap.push(ii(0, 1));
  35.         while (heap.size()) {
  36.             int u = heap.top().second, du = heap.top().first; heap.pop();
  37.             if (du != dist[u]) continue;
  38.             for (int i = 0; i < (int) adj[u].size(); ++i) {
  39.                 int v = adj[u][i].second, uv = adj[u][i].first;
  40.                 if (dist[v] > du + uv) { dist[v] = du + uv; heap.push(ii(du+uv, v)); }
  41.             }
  42.         }
  43.  
  44.         int res = -1;
  45.         for (int ver : lisDoor) res = (res == -1) ? dist[ver] : min(res, dist[ver]);
  46.         return res;
  47.     }
  48. }
  49.  
  50. int par[N];
  51.  
  52. int getRoot(int u) { return (par[u] < 0) ? u : (par[u] = getRoot(par[u])); }
  53. bool Merge(int u, int v) {
  54.     u = getRoot(u); v = getRoot(v);
  55.     if (u == v) return false;
  56.     if (par[u] > par[v]) swap(u, v);
  57.     par[u] += par[v]; par[v] = u;
  58.     return true;
  59. }
  60.  
  61. priority_queue<dataHeap, vector<dataHeap>, greater<dataHeap> > pq;
  62. int d[N][4], root[N][4];
  63.  
  64. void Dijkstra1() {
  65.     for (int i = 1; i <= n; ++i) for (int j = 1; j <= 2; ++j) d[i][j] = oo, root[i][j] = -1;
  66.     for (int u : lisDoor) {
  67.         d[u][1] = 0; root[u][1] = getRoot(u);
  68.         pq.push(dataHeap(u, 1, d[u][1]));
  69.     }
  70.    
  71.     while (pq.size()) {
  72.         int u = pq.top().u, type = pq.top().type, val = pq.top().val; pq.pop();
  73.         if (val != d[u][type]) continue;
  74.         for (int i = 0; i < (int) adj[u].size(); ++i) {
  75.             int v = adj[u][i].second, cost = adj[u][i].first;
  76.             if (d[v][1] > val + cost) {
  77.                 d[v][1] = val + cost; root[v][1] = root[u][type];
  78.                 pq.push(dataHeap(v, 1, d[v][1]));
  79.             }
  80.         }
  81.     }
  82. }
  83. void Dijkstra2() {
  84.     for (int i = 1; i <= n; ++i) pq.push(dataHeap(i, 1, d[i][1]));
  85.     while (pq.size()) {
  86.         int u = pq.top().u, type = pq.top().type, val = pq.top().val; pq.pop();
  87.         if (val != d[u][type]) continue;
  88.         for (int i = 0; i < (int) adj[u].size(); ++i) {
  89.             int v = adj[u][i].second, cost = adj[u][i].first;
  90.             if (d[v][2] > val+cost && root[u][type] != root[v][1]) {
  91.                 d[v][2] = val+cost; root[v][2] = root[u][type];
  92.                 pq.push(dataHeap(v, 2, d[v][2]));
  93.             }
  94.         }
  95.     }
  96. }
  97.  
  98. vector<dataEdge> Edge;
  99. int Trace[N], best[N];
  100.  
  101. void sol() {
  102.     int Add = Min_Distance_To_Tree::Dijkstra(), res = 0;
  103.  
  104.     for (int i = 1; i <= n; ++i) par[i] = -1;
  105.     while (true) {
  106.         Dijkstra1(); Dijkstra2();
  107.  
  108.         for (int i = 1; i <= n; ++i) best[i] = oo, Trace[i] = -1;
  109.  
  110.         for (int ver : lisDoor) {
  111.             int u = getRoot(ver), v = root[ver][2], w = d[ver][2];
  112.             if (best[u] > w) { best[u] = w; Trace[u] = v; }
  113.             if (best[v] > w) { best[v] = w; Trace[v] = v; }
  114.         }
  115.  
  116.         Edge.clear();
  117.         for (int ver : lisDoor) {
  118.             int u = getRoot(ver);
  119.             if (Trace[u] == -1) continue;
  120.             int v = Trace[u], w = best[u];
  121.             Edge.push_back(dataEdge(u, v, w));
  122.         }
  123.  
  124.         sort(Edge.begin(), Edge.end());
  125.         for (dataEdge foo : Edge) {
  126.             int u = foo.u, v = foo.v, w = foo.w;
  127.             if (Merge(u, v)) res += w;
  128.         }
  129.  
  130.         int Count = 0;
  131.         for (int i : lisDoor) Count += (par[i] < 0);
  132.         if (Count == 1) break;     
  133.     }
  134.  
  135.     cout << res + Add << '\n';
  136. }
  137.  
  138. #undef int
  139. int main() {
  140. #define int                     long long
  141.     freopen("input.txt", "r", stdin);
  142.  
  143.     Read(n); Read(m);
  144.     int u, v, w;
  145.     for (int i = 1; i <= m; ++i) {
  146.         Read(u); Read(v); Read(w);
  147.         adj[u].push_back(ii(w, v)); adj[v].push_back(ii(w, u));
  148.     }
  149.     Read(numDoor);
  150.     for (int i = 1; i <= numDoor; ++i) Read(u), lisDoor.push_back(u);
  151.  
  152.     sol();
  153.  
  154.     return 0;
  155. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement