Advertisement
Guest User

Untitled

a guest
Jun 13th, 2018
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.62 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. typedef pair<int,int> ii;
  6. typedef pair<int,ii> data;
  7. #define fi first
  8. #define se second
  9.  
  10. const int N = 25e4 + 5;
  11.  
  12. int n, m, k;
  13. vector<ii> adj[N];
  14. int a[N];
  15. int f[N], root[N];
  16. bool visit[N];
  17. int res[N];
  18. priority_queue<data, vector<data>, greater<data> > pq;
  19.  
  20. void solve(int u) {
  21.     if (visit[u]) return;
  22.     visit[u] = true;
  23.     long long val = 0;
  24.     for (auto v : adj[u]) {
  25.         if (root[v.fi] == root[u]) {
  26.             if (f[v.fi] + v.se == f[u]) continue;
  27.             val += 2LL * v.se;
  28.             solve(v.fi);
  29.         }
  30.         else {
  31.             int tmp = f[u] + f[v.fi] + v.se;
  32.             val += tmp - 2LL * f[u];
  33.         }
  34.     }
  35.     res[root[u]] += val;
  36. }
  37.  
  38. signed main() {
  39.     ios_base::sync_with_stdio(false);
  40.     cin >> n >> m;
  41.     for (int i = 1;i <= m;++i) {
  42.         int u, v, w; cin >> u >> v >> w;
  43.         adj[u].push_back({v, w}), adj[v].push_back({u, w});
  44.     }
  45.     for (int i = 1;i <= n;++i) f[i] = 1e18, root[i] = n + 1;
  46.     cin >> k;
  47.     for (int i = 1;i <= k;++i) {
  48.         cin >> a[i];
  49.         f[a[i]] = 0, root[a[i]] = a[i];
  50.         pq.push({0, {a[i], a[i]}});
  51.     }
  52.     while (!pq.empty()) {
  53.         data cur = pq.top(); pq.pop();
  54.         if (root[cur.se.se] != cur.se.fi || f[cur.se.se] != cur.fi) continue;
  55.         int u = cur.se.se;
  56.         for (auto v : adj[u]) {
  57.             if (f[v.fi] > f[u] + v.se || (f[v.fi] == f[u] + v.se && root[u] < root[v.fi])) {
  58.                 f[v.fi] = f[u] + v.se, root[v.fi] = root[u];
  59.                 pq.push({f[v.fi], {root[v.fi], v.fi}});
  60.             }
  61.         }
  62.     }
  63.     // for (int i = 1;i <= n;++i) cout << root[i] << '\n';
  64.     for (int i = 1;i <= k;++i) {
  65.         solve(a[i]); cout << res[a[i]] / 2LL;
  66.         if (res[a[i]] & 1LL) cout << ".5" << '\n';
  67.         else cout << ".0" << '\n';
  68.     }
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement