fork download
copy 
  1. //NiceDuck
  2. #include "bits/stdc++.h"
  3. typedef long long ll;
  4. using namespace std;
  5. #define FILE "000"
  6. #define foru(i,a,b) for(int i=(int)(a); i<=(int)(b); ++i)
  7. #define ford(i,a,b) for(int i=(int)(a); i>=(int)(b); --i)
  8. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);
  9. #define pb push_back
  10. #define fi first
  11. #define se second
  12. #define el "\n"
  13. #define MASK(i) (1LL<<(i))
  14. #define BIT(i,j) (((i)>>(j))&1)
  15. #define TIME 1.0*clock()/CLOCKS_PER_SEC
  16. #define LOG 20
  17.  
  18. const ll MAX=2e5+5;
  19. int n,m,q;
  20. struct AdjList
  21. {
  22.     int v; ll w; int idx;
  23. };
  24. vector<AdjList> adj[MAX];
  25.  
  26. int num[MAX],low[MAX],timer=0;
  27. stack<int> st;
  28. int compCount=0,compID[MAX];
  29. void tarjan(int u, int id)
  30. {
  31.     num[u]=low[u]=++timer;
  32.     st.push(u);
  33.     for(AdjList tmp:adj[u])
  34.     {
  35.         int v=tmp.v, idx=tmp.idx;
  36.         if(idx==id) continue;
  37.         if(num[v]) low[u]=min(low[u],num[v]);
  38.         else
  39.         {
  40.             tarjan(v,idx);
  41.             low[u]=min(low[u],low[v]);
  42.             if(low[v]>num[u])
  43.             {
  44.                 ++compCount;
  45.                 while(true)
  46.                 {
  47.                     int t=st.top();
  48.                     st.pop();
  49.                     compID[t]=compCount;
  50.                     if(t==v) break;
  51.                 }
  52.             }
  53.         }
  54.     }
  55. }
  56. vector<pair<int,ll>> adjTree[MAX];
  57. int logn,jump[LOG][MAX],h[MAX];
  58. ll dist[LOG][MAX];
  59. void dfs(int u, int p)
  60. {
  61.     for(pair<int,ll> tmp:adjTree[u])
  62.     {
  63.         int v=tmp.fi; ll w=tmp.se;
  64.         if(v==p) continue;
  65.         h[v]=h[u]+1;
  66.         jump[0][v]=u;
  67.         dist[0][v]=w;
  68.         dfs(v,u);
  69.     }
  70. }
  71. void buildLCA()
  72. {
  73.     dfs(1,0);
  74.     logn=31-__builtin_clz(compCount);
  75.     foru(j,1,logn)
  76.     {
  77.         foru(i,1,compCount)
  78.         {
  79.             int t=jump[j-1][i];
  80.             jump[j][i]=jump[j-1][t];
  81.             dist[j][i]=dist[j-1][i]+dist[j-1][t];
  82.         }
  83.     }
  84. }
  85. ll calc(int u, int v)
  86. {
  87.     u=compID[u]; v=compID[v];
  88.     if(u==v) return 0;
  89.     if(h[u]>h[v]) swap(u,v);
  90.     int k=h[v]-h[u];
  91.     ll ans=0;
  92.     ford(j,logn,0)
  93.     {
  94.         if(BIT(k,j))
  95.         {
  96.             ans+=dist[j][v];
  97.             v=jump[j][v];
  98.         }
  99.     }
  100.     if(u==v) return ans;
  101.     ford(j,logn,0)
  102.     {
  103.         if(jump[j][u]!=jump[j][v])
  104.         {
  105.             ans+=dist[j][u]+dist[j][v];
  106.             u=jump[j][u];
  107.             v=jump[j][v];
  108.         }
  109.     }
  110.     return ans+dist[0][u]+dist[0][v];
  111. }
  112.  
  113. int main()
  114. {
  115.     fastio
  116.     if(fopen(FILE ".inp","r"))
  117.     {
  118.         freopen(FILE ".inp","r",stdin); freopen(FILE ".out","w",stdout);
  119.     }
  120.     cin>>n>>m>>q;
  121.     foru(i,1,m)
  122.     {
  123.         int u,v; ll w; cin>>u>>v>>w;
  124.         adj[u].pb({v,w,i});
  125.         adj[v].pb({u,w,i});
  126.     }
  127.     tarjan(1,0);
  128.     if(!st.empty())
  129.     {
  130.         ++compCount;
  131.         while(!st.empty())
  132.         {
  133.             int u=st.top(); st.pop();
  134.             compID[u]=compCount;
  135.         }
  136.     }
  137.     foru(i,1,n)
  138.     {
  139.         for(AdjList tmp:adj[i])
  140.         {
  141.             int u=i;
  142.             int v=tmp.v;
  143.             ll w=tmp.w;
  144.             int idU=compID[u], idV=compID[v];
  145.             if(idU!=idV)
  146.             {
  147.                 adjTree[idU].pb({idV,w});
  148.             }
  149.         }
  150.     }
  151.     buildLCA();
  152.     while(q--)
  153.     {
  154.         int u,v; cin>>u>>v;
  155.         cout<<calc(u,v)<<el;
  156.     }
  157.     return 0;
  158. }
  159.  
Success #stdin #stdout 0.01s 17096KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2r4Oxu
language:
C++14 (gcc 8.3)
created:
1 hour 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!