fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define ll long long
  6. #define bit(n, i) ((n >> i) & 1)
  7. #define all(a) a.begin(), a.end()
  8. #define rep(i, x, n) for (int i = x; i <= n; ++i)
  9. #define red(i, x, n) for (int i = x; i >= n; --i)
  10. #define inp(a) freopen(a".inp", "r", stdin), freopen(a".out", "w", stdout)
  11.  
  12. template<class A, class B> inline bool maxi(A &x, B y) {return (x < y ? x = y, 1 : 0);};
  13. template<class A, class B> inline bool mini(A &x, B y) {return (x > y ? x = y, 1 : 0);};
  14.  
  15. const int N = 1e5 + 5;
  16. const ll MOD = 1e9 + 7;
  17. const ll INF = 1e11 + 642009;
  18.  
  19. // main program
  20.  
  21. struct DSU {
  22.     int n;
  23.     vector<int> lab;
  24.  
  25.     void init(int _n){
  26.         n = _n;
  27.         lab.assign(n + 1, -1);
  28.     }
  29.  
  30.     int get(int u){
  31.         return lab[u] < 0 ? u : lab[u] = get(lab[u]);
  32.     }
  33.  
  34.     bool unite(int u, int v){
  35.         u = get(u); v = get(v);
  36.  
  37.         if (u == v) return 0;
  38.         if (lab[u] > lab[v]) swap(u, v);
  39.  
  40.         lab[u] += lab[v];
  41.         lab[v] = u;
  42.  
  43.         return 1;
  44.     }
  45. } dsu;
  46.  
  47. struct node {int v, w;};
  48. struct edge {int u, v, w;};
  49.  
  50. struct element {
  51.     int u; ll d;
  52.  
  53.     bool operator <(const element &other) const {
  54.         return d > other.d;
  55.     }
  56. };
  57.  
  58. const int LOG = 17;
  59.  
  60. int n, m, t;
  61. bool used[N];
  62. vector<int> nodes;
  63. vector<edge> edges;
  64. vector<node> a[N], b[N];
  65.  
  66. int h[N], p[LOG + 1][N];
  67. ll d[N], dist[60][N];
  68.  
  69. void dfs(int u){
  70.     for (auto [v, w]: b[u]){
  71.         if (v == p[0][u]) continue;
  72.  
  73.         p[0][v] = u; 
  74.         h[v] = h[u] + 1;
  75.         d[v] = d[u] + w;
  76.  
  77.         rep(i, 1, LOG) p[i][v] = p[i - 1][p[i - 1][v]];
  78.  
  79.         dfs(v);
  80.     }
  81. }
  82.  
  83. int LCA(int u, int v){
  84.     if (h[v] > h[u]) swap(u, v);
  85.     int k = h[u] - h[v];
  86.  
  87.     red(i, LOG, 0) if (bit(k, i)) u = p[i][u];
  88.  
  89.     if (u == v) return v;
  90.  
  91.     red(i, LOG, 0) if (p[i][u] != p[i][v]){
  92.         u = p[i][u]; v = p[i][v];
  93.     }
  94.  
  95.     return p[0][u];
  96. }
  97.  
  98. ll distLCA(int u, int v){
  99.     return d[u] + d[v] - 2 * d[LCA(u, v)];
  100.  
  101. }
  102.  
  103. priority_queue<element> q;
  104.  
  105. void dijkstra(int i, int s){
  106.     rep(u, 1, n) dist[i][u] = INF;
  107.     dist[i][s] = 0; q.push({s, 0});
  108.  
  109.     while (q.size()){
  110.         auto [u, du] = q.top(); q.pop();
  111.  
  112.         if (du != dist[i][u]) continue;
  113.  
  114.         for (auto [v, w]: a[u]){
  115.             if (dist[i][v] > dist[i][u] + w){
  116.                 dist[i][v] = dist[i][u] + w;
  117.  
  118.                 q.push({v, dist[i][v]});
  119.             }
  120.         }
  121.     }
  122. }
  123.  
  124. ll query(int u, int v){
  125.     ll d1 = distLCA(u, v);
  126.     ll d2 = INF;
  127.  
  128.     if (nodes.size() > 0){
  129.         rep(i, 0, (int)nodes.size() - 1) rep(j, i + 1, (int)nodes.size() - 1){
  130.             mini(d2, dist[i][u] + dist[i][nodes[j]] + dist[j][v]);
  131.             mini(d2, dist[j][u] + dist[i][nodes[j]] + dist[i][v]);
  132.         }
  133.     }
  134.  
  135.     return min(d1, d2);
  136. }
  137. signed main(){
  138.     cin.tie(0) -> sync_with_stdio(0);
  139.  
  140.     cin >>n >>m >>t;
  141.  
  142.     rep(i, 1, m){
  143.         int u, v, w; cin >>u >>v >>w;
  144.  
  145.         edges.pb({u, v, w});
  146.         a[u].pb({v, w}); a[v].pb({u, w});
  147.     }    
  148.  
  149.     sort(all(edges), [](const edge &a, const edge &b){
  150.         return a.w < b.w;
  151.     });
  152.  
  153.     dsu.init(n);
  154.  
  155.     for (auto [u, v, w]: edges){
  156.         if (dsu.unite(u, v)){
  157.             b[u].pb({v, w}); b[v].pb({u, w});
  158.         } else {
  159.             if (used[u] == 0) nodes.pb(u), used[u] = 1;
  160.             if (used[v] == 0) nodes.pb(v), used[v] = 1;
  161.         }
  162.     }   
  163.  
  164.     dfs(1); 
  165.     rep(i, 0, (int)nodes.size() - 1) dijkstra(i, nodes[i]);
  166.  
  167.     while (t--){
  168.         int u, v; cin >>u >>v;
  169.  
  170.         cout <<query(u, v) <<'\n';
  171.     }
  172.  
  173.     return 0;
  174. }
Success #stdin #stdout 0.01s 8680KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/kloa4j
language:
C++ (gcc 8.3)
created:
11 days 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!