fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 100100;
  5. const int logN = 20;
  6.  
  7. int p[N];
  8. int tin[N], tout[N];
  9. int T = 0;
  10. int fup[N][logN];
  11. int dist[N];
  12. vector<pair<int, int>> g[N];
  13.  
  14. int dsu_get (int v) {
  15. 	return (v == p[v]) ? v : (p[v] = dsu_get (p[v]));
  16. }
  17.  
  18. void dsu_unite (int a, int b) {
  19. 	a = dsu_get (a);
  20. 	b = dsu_get (b);
  21. 	if (rand() & 1)
  22. 		swap (a, b);
  23. 	if (a != b)
  24. 		p[a] = b;
  25. }
  26.  
  27. void dfs(int v, int u, int d)
  28. {
  29.     dist[v] = d;
  30.     tin[v] = T++;      
  31.     fup[v][0] = u;
  32.     for(int i = 1; i < logN; i++)
  33.         fup[v][i] = fup[fup[v][i - 1]][i - 1];
  34.     for(auto [y, w] : g[v])
  35.         if(y != u)
  36.             dfs(y, v, d + w);
  37.     tout[v] = T++;   
  38. }
  39.  
  40. bool is_ancestor(int u, int v)
  41. {
  42.     return tin[u] <= tin[v] && tout[u] >= tout[v];
  43. }
  44.  
  45. int LCA(int x, int y)
  46. {
  47.     if(is_ancestor(x, y)) return x;
  48.     for(int i = logN - 1; i >= 0; i--)
  49.         if(!is_ancestor(fup[x][i], y))
  50.             x = fup[x][i];
  51.     return fup[x][0];
  52. }
  53.  
  54. int main() {
  55.     int n,m;
  56.     cin >> n >> m;
  57.  
  58.     vector<pair<int,pair<int,int>>> e;
  59.     for (int i = 0; i < m; ++i) {
  60.         int u,v,w;
  61.         cin >>u>>v>>w;
  62.         e.push_back({w,{u,v}});
  63.     }
  64.  
  65.     int cost = 0, cnt = 0;
  66.     sort(e.begin(), e.end());
  67.     for (int i = 1; i <= n; ++i) p[i] = i;
  68.     for (int i = 0; i < m; ++i) {
  69.         int u = e[i].second.first,  v = e[i].second.second,  w = e[i].first;
  70.         if (dsu_get(u) != dsu_get(v)) {
  71.             cost += w;
  72.             ++cnt;
  73.             g[u].push_back ({v,w});
  74.             g[v].push_back ({u,w});
  75.             dsu_unite (u, v);
  76.         }
  77.     }
  78.  
  79.     if (cnt != n - 1) {
  80.         cout << "Impossible" << endl;
  81.         return 0;
  82.     }
  83.     cout << cost << endl;
  84.  
  85.     int q;
  86.     cin >> q;
  87.     dfs(1, 1, 0);
  88.     while (q--) {
  89.         int u,v;
  90.         cin >>u>>v;
  91.  
  92.         int lca = LCA(u, v);
  93.         int ans = dist[u] - 2*dist[lca] + dist[v];
  94.         cout <<ans<<endl;
  95.     }
  96.  
  97.     return 0;
  98. }
Success #stdin #stdout 0.01s 7148KB
comments (?)
stdin
copy 
5 7
1 2 5
1 3 10
2 3 20
3 5 30
3 4 25
4 5 35
1 5 15
4
1 2
3 5
1 5
2 4
stdout
copy 
55
5
25
15
40
https://ideone.com/MXwF2G
language:
C++14 (clang 8.0)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!