fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  3. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  4. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  5. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  6. #define ll long long
  7. #define el "\n"
  8. #define fi first
  9. #define se second
  10. #define _ROOT_ int main()
  11. #define M 1000000007
  12. #define MAXN 201001
  13. #define INF (1ll<<60)
  14. #define LOG 21
  15. #define NAME "EXIT"
  16. #define debug(a) cout << #a << " = " << a << endl;
  17. using namespace std;
  18.  
  19. ll n, m, k, x, q   ;
  20. ll a[MAXN] ;
  21. ll p[MAXN ] ;
  22. ll d[MAXN] ;
  23. ll high[MAXN ] ;
  24. ll lab[MAXN ] ;
  25. vector<pair<ll,ll> > adj_tree[MAXN ] ;
  26. vector<pair<ll,ll> > adj[MAXN ] ;
  27. vector<ll> spec ;
  28.  
  29. ll par[MAXN][LOG + 1 ] ;
  30. ll mi[MAXN][LOG + 1 ] ;
  31.  
  32. ll find_set(ll a ) {
  33.     return lab[a] < 0 ? a : lab[a] = find_set(lab[a]) ;
  34. }
  35. bool union_set(ll a, ll b ) {
  36.     a = find_set(a) ;
  37.     b = find_set(b) ;
  38.     if(a == b ) return false ;
  39.     if(lab[a] > lab[b]) swap(a, b) ;
  40.     lab[a] += lab[b] ;
  41.     lab[b] = a ;
  42.     return true ;
  43. }
  44.  
  45. struct Edge {
  46.     ll u, v, w ;
  47.     bool operator < (const Edge & other ) const {
  48.         return w > other.w ;
  49.     }
  50. };
  51. Edge edge[MAXN ] ;
  52.  
  53. bool Dijkstra( ) {
  54.     FOR(i, 1, n ) d[i] = INF ;
  55.     priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
  56.     for(ll i : spec ) {
  57.         pq.push({0, i}) ;
  58.         d[i] = 0 ;
  59.     }
  60.     while(!pq.empty() ) {
  61.         pair<ll,ll> u = pq.top() ;
  62.         pq.pop() ;
  63.         if(d[u.se ] < u.fi ) continue ;
  64.         for(auto [v, w ] : adj[u.se ]) if(d[v] > u.fi + w ) pq.push({d[v] = u.fi + w, v }) ;
  65.     }
  66.     FOR(i, 1, k ) if(d[p[i]] > x ) return false ;
  67.     return true ;
  68. }
  69.  
  70. ll query(ll u, ll v ) {
  71.     if(u == v ) return d[u] ;
  72.     if(high[u] < high[v]  ) swap(u, v) ;
  73.     ll res = INF ;
  74.     FORD(i, LOG, 0 ) if(high[par[u][i]] >= high[v] ) {
  75.         res = min(res, mi[u][i] ) ;
  76.         u = par[u][i] ;
  77.     }
  78.     if(u == v ) return res ;
  79.     FORD(i, LOG, 0 )
  80.     if(par[v][i] != par[u][i]) {
  81.         res = min(res, mi[v][i]) ;
  82.         res = min(res, mi[u][i]) ;
  83.         u = par[u][i] ;
  84.         v = par[v][i] ;
  85.     }
  86.     return min ( { res, mi[u][0], mi[v][0] } ) ;
  87. }
  88.  
  89. void dfs(ll u, ll p ) {
  90.     for(pair<ll,ll> v : adj_tree[u]) if(v.fi != p ) {
  91.             par[v.fi][0] = u ;
  92.             mi[v.fi][0] = v.se ;
  93.             FOR(i, 1, LOG ) {
  94.                 par[v.fi][i] = par[ par[v.fi][i - 1]][i - 1 ] ;
  95.                 mi[v.fi][i] = min(mi[v.fi][i - 1], mi[par[v.fi][i - 1] ][i - 1 ] ) ;
  96.             }
  97.             high[v.fi] = high[u] + 1 ;
  98.             dfs(v.fi, u ) ;
  99.  
  100.         }
  101. }
  102.  
  103. void init() {
  104.     cin >> n >> m  ;
  105.     FOR(i, 1, m ) {
  106.         ll u, v, w ;
  107.         cin >> u >> v >> w ;
  108.         edge[i] = {u, v, w } ;
  109.         adj[u].push_back({ v, w }) ;
  110.         adj[v].push_back({ u, w }) ;
  111.     }
  112.     cin >> k ;
  113.     FOR(i, 1, k ) {
  114.         ll x ;
  115.         cin >> x ;
  116.         spec.push_back(x) ;
  117.     }
  118.     cin >> q ;
  119. }
  120.  
  121.  
  122. void solve() {
  123.     Dijkstra() ;
  124. //    FOR(i , 1 , n ) debug(d[i]) ;
  125.     FOR(i, 1, m ) edge[i].w = min(d[edge[i].u], d[edge[i].v ] ) ;
  126.  
  127.     memset(lab, - 1, sizeof lab ) ;
  128.     sort(edge + 1, edge + m + 1 ) ;
  129.  
  130.     FOR(i, 1, m ) {
  131.         if(union_set(edge[i].u, edge[i].v )) {
  132. //            cout << edge[i].u << " " << edge[i].v << " " << edge[i].w << el ;
  133.             adj_tree[edge[i].u].push_back({edge[i].v, edge[i].w }) ;
  134.             adj_tree[edge[i].v].push_back({edge[i].u, edge[i].w }) ;
  135.         }
  136.     }
  137. //    cout << " r" << el ;
  138.     FOR(i, 0, n ) FOR(j, 0, LOG ) mi[i][j] = INF ;
  139.     high[0] = - 1;
  140.     dfs(1, 1 ) ;
  141.     FOR(cnt, 1, q ) {
  142.         ll u, v ;
  143.         cin >> u >> v ;
  144.         cout << query(u, v ) << el ;
  145.     }
  146. }
  147.  
  148. _ROOT_ {
  149.     // freopen(NAME".inp" , "r" , stdin);
  150.    //  freopen(NAME".out" , "w", stdout) ;
  151.     ios_base::sync_with_stdio(0);
  152.     cin.tie(0);
  153.     cout.tie(0);
  154.     int t = 1; // cin >> t ;
  155.     while(t--) {
  156.         init();
  157.         solve();
  158.     }
  159.     return (0&0);
  160. }
  161.  
Success #stdin #stdout 0.01s 17868KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4HQEsR
language:
C++14 (gcc 8.3)
created:
22 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!