fork download
copy 
  1. #include<bits/stdc++.h>                                                         
  2. using namespace std;                                                            
  3.  
  4. const long long INF = 4e18;                                                     
  5.  
  6.  
  7. vector<pair<long long,long long>> graf[200005];                                 
  8.  
  9. vector<pair<long long,long long>> tre[200005];                                  
  10. vector<pair<pair<long long,long long>,long long>> kra;                          
  11.  
  12.  
  13. long long odw[200005];                                                          
  14.  
  15. long long koszt[30][200005];                                                    
  16.  
  17. long long jump[200005][25];                                                     
  18.  
  19. long long ile[200005];                                                          
  20.  
  21. long long pre[100005], post[100005];                                            
  22. long long timer = 0;                                                            
  23.  
  24.  
  25. void dij(long long id, long long start)                                         
  26. {                                                                               
  27.     for (int i = 1; i <= 200000; i++)                                           
  28.         koszt[id][i] = INF;                                                     
  29.  
  30.     priority_queue<pair<long long,long long>> pq;                               
  31.     koszt[id][start] = 0;                                                       
  32.     pq.push({0, start});                                                        
  33.  
  34.     while (!pq.empty())                                                         
  35.     {                                                                           
  36.         long long d = -pq.top().first;                                          
  37.         long long v = pq.top().second;                                          
  38.         pq.pop();                                                               
  39.  
  40.         if (d != koszt[id][v]) continue;                                        
  41.  
  42.         for (auto e : graf[v])                                                  
  43.         {                                                                       
  44.             if (koszt[id][e.first] > d + e.second)                              
  45.             {                                                                   
  46.                 koszt[id][e.first] = d + e.second;                              
  47.                 pq.push({-(d + e.second), e.first});                            
  48.             }                                                                   
  49.         }                                                                       
  50.     }                                                                           
  51. }                                                                               
  52.  
  53.  
  54. void dfs(long long v, long long p)                                              
  55. {                                                                               
  56.     odw[v] = 1;                                                                 
  57.     for (auto e : graf[v])                                                      
  58.     {                                                                           
  59.         if (e.first == p) continue;                                             
  60.  
  61.         if (odw[e.first])                                                       
  62.         {                                                                       
  63.             kra.push_back({{v, e.first}, e.second});                            
  64.         }                                                                       
  65.         else                                                                    
  66.         {                                                                       
  67.             tre[v].push_back(e);                                                
  68.             tre[e.first].push_back({v, e.second});                              
  69.             dfs(e.first, v);                                                    
  70.         }                                                                       
  71.     }                                                                           
  72. }                                                                               
  73.  
  74.  
  75. void dfs1(long long v, long long p)                                             
  76. {                                                                               
  77.     pre[v] = ++timer;                                                           
  78.  
  79.     for (auto e : tre[v])                                                       
  80.     {                                                                           
  81.         if (e.first == p) continue;                                             
  82.         jump[e.first][0] = v;                                                   
  83.         ile[e.first] = ile[v] + e.second;                                       
  84.         dfs1(e.first, v);                                                       
  85.     }                                                                           
  86.  
  87.     post[v] = ++timer;                                                          
  88. }                                                                               
  89.  
  90.  
  91. bool ancestor(long long a, long long b)                                         
  92. {                                                                               
  93.     return pre[a] <= pre[b] && post[a] >= post[b];                              
  94. }                                                                               
  95.  
  96. long long lca(long long a, long long b)                                         
  97. {                                                                               
  98.     if (ancestor(a, b)) return a;                                               
  99.     if (ancestor(b, a)) return b;                                               
  100.  
  101.     for (int i = 20; i >= 0; i--)                                               
  102.     {                                                                           
  103.         if (jump[a][i] && !ancestor(jump[a][i], b))                             
  104.             a = jump[a][i];                                                     
  105.     }                                                                           
  106.     return jump[a][0];                                                          
  107. }                                                                               
  108.  
  109. int main()                                                                      
  110. {                                                                               
  111.     ios::sync_with_stdio(0);                                                    
  112.     cin.tie(0);                                                                 
  113.  
  114.     long long n, m;                                                             
  115.     cin >> n >> m;                                                              
  116.  
  117.     for (int i = 0; i < m; i++)                                                 
  118.     {                                                                           
  119.         long long a, b, c;                                                      
  120.         cin >> a >> b >> c;                                                     
  121.         graf[a].push_back({b, c});                                              
  122.         graf[b].push_back({a, c});                                              
  123.     }                                                                           
  124.  
  125.     dfs(1, 0);                                                                  
  126.  
  127.     for (int i = 0; i < (int)kra.size(); i++)                                   
  128.         dij(i, kra[i].first.first);                                             
  129.  
  130.     dfs1(1, 0);                                                                 
  131.  
  132.     for (int i = 1; i <= 20; i++)                                               
  133.         for (int j = 1; j <= n; j++)                                            
  134.             jump[j][i] = jump[jump[j][i-1]][i-1];                               
  135.  
  136.     int q;                                                                      
  137.     cin >> q;                                                                   
  138.  
  139.     while (q--)                                                                 
  140.     {                                                                           
  141.         long long a, b;                                                         
  142.         cin >> a >> b;                                                          
  143.  
  144.         long long ans = ile[a] + ile[b] - 2 * ile[lca(a, b)];                   
  145.  
  146.         for (int i = 0; i < (int)kra.size(); i++)                               
  147.         {                                                                       
  148.             ans = min(ans,                                                      
  149.  
  150.                 koszt[i][a] + koszt[i][b]);                     
  151.         }                                                                       
  152.  
  153.         cout << ans << '\n';                                                    
  154.     }                                                                           
  155. }
Success #stdin #stdout 0.01s 22384KB
comments (?)
stdin
copy 
7 7
1 2 1
2 3 2
2 4 3
4 5 3
4 7 1
6 7 2
1 6 3
1
3 3
stdout
copy 
0
https://ideone.com/yLbxX2
language:
C++ (gcc 8.3)
created:
4 hours 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!