fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef unsigned long long ull;
  6.  
  7. #define rep(i, n) for(int i = 1; (i) <= (n); ++i)
  8. #define forn(i, l, r) for(int i = (l); i <= (r); ++i)
  9. #define ford(i, r, l) for(int i = (r); i >= (l); --i)
  10. #define FOR(i, n) for(int i = 0; i < (n); ++i)
  11. #define FORD(i, n) for(int i = ((n) - 1); i >= 0; --i)
  12. #define fi first
  13. #define se second
  14. #define pii pair<int, int>
  15. #define pll pair<ll, ll>
  16. #define pb push_back
  17. #define endl "\n"
  18. #define task "walk"
  19. #define sz(a) int(a.size())
  20. #define C(x, y) make_pair(x, y)
  21. #define all(a) (a).begin(), (a).end()
  22. #define bit(i, mask) (mask >> i & 1)
  23.  
  24. template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
  25. template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
  26.  
  27. inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
  28. inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
  29. inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}
  30.  
  31. const int N = 1e5 + 3;
  32. const int M = 5e5;
  33. const int LOG = 16;
  34. const int MOD = 1e9 + 7;
  35. const int INF = 1e9 + 33;
  36. const int S = 375;
  37.  
  38. int n, m, k, q;
  39.  
  40. int D[N], b[N];
  41. vector<pii> g[N];
  42. int par[N], sz[N];
  43.  
  44. int root(int u) {return u == par[u] ? u : par[u] = root(par[u]);}
  45. bool union_set(int u, int v)
  46. {
  47.     if((u = root(u)) == (v = root(v))) return 0;
  48.     if(sz[u] < sz[v]) swap(u, v);
  49.     par[v] = u;
  50.     sz[u] += sz[v];
  51.  
  52.     return 1;
  53. }
  54. void Dijkstra()
  55. {
  56.     priority_queue<pii, vector<pii>, greater<pii>> q;
  57.     rep(i, n)
  58.     {
  59.         if(b[i]) D[i] = 0, q.push({0, i});
  60.         else D[i] = INF;
  61.     }
  62.     while(sz(q))
  63.     {
  64.         pii tmp = q.top();
  65.         q.pop();
  66.         int dist = tmp.fi, u = tmp.se;
  67.         if(D[u] != dist) continue;
  68.  
  69.         for(auto &[v, w] : g[u])
  70.             if(minimize(D[v], D[u] + w))
  71.             q.push({D[v], v});
  72.     }
  73. }
  74.  
  75. int tin[N], tout[N], timedfs = 0;
  76. int up[N][LOG + 1], min_edge[N][LOG + 1];
  77.  
  78. void dfs(int u, int p = 1, int w = INF)
  79. {
  80.     tin[u] = ++timedfs;
  81.     up[u][0] = p;
  82.     min_edge[u][0] = w;
  83.     forn(i, 1, LOG)
  84.     {
  85.         up[u][i] = up[up[u][i - 1]][i - 1];
  86.         min_edge[u][i] = min(min_edge[u][i - 1], min_edge[up[u][i - 1]][i - 1]);
  87.     }
  88.  
  89.     for(auto &[v, wei] : g[u])
  90.     if(v != p)
  91.     {
  92.         dfs(v, u, wei);
  93.     }
  94.     tout[u] = ++timedfs;
  95. }
  96.  
  97. bool is_anc(int u, int v)
  98. {
  99.     return tin[u] <= tin[v] && tout[v] <= tout[u];
  100. }
  101.  
  102. int get(int u, int v)
  103. {
  104.     int res = INF;
  105.     if(is_anc(u, v)) swap(u, v);
  106.  
  107.     ford(i, LOG, 0) if(!is_anc(up[u][i], v))
  108.         res = min(res, min_edge[u][i]), u = up[u][i];
  109.     if(!is_anc(u, v))
  110.         res = min(res, min_edge[u][0]), u = up[u][0];
  111.  
  112.     ford(i, LOG, 0) if(!is_anc(up[v][i], u))
  113.         res = min(res, min_edge[v][i]), v = up[v][i];
  114.     if(!is_anc(v, u))
  115.         res = min(res, min_edge[v][0]);
  116.     return res;
  117. }
  118.  
  119. array<int, 3> e[M];
  120.  
  121. void solve()
  122. {
  123.     cin >> n >> m >> k >> q;
  124.     rep(i, m)
  125.     {
  126.         int u, v, w;
  127.         cin >> u >> v >> w;
  128.         g[u].pb({v, w});
  129.         g[v].pb({u, w});
  130.         e[i] = {w, u, v};
  131.     }
  132.     rep(i, k)
  133.     {
  134.         int x;
  135.         cin >> x;
  136.         b[x] = 1;
  137.     }
  138.  
  139.     Dijkstra();
  140.     rep(i, n) g[i].clear();
  141.  
  142.     rep(i, m)
  143.         e[i][0] = min(D[e[i][1]], D[e[i][2]]);
  144.     sort(e + 1, e + 1 + m);
  145.     rep(i, n) par[i] = i, sz[i] = 1;
  146.     ford(i, m, 1) if(union_set(e[i][1], e[i][2]))
  147.     {
  148.         g[e[i][1]].pb({e[i][2], e[i][0]});
  149.         g[e[i][2]].pb({e[i][1], e[i][0]});
  150.     }
  151.     dfs(1);
  152.     rep(i, q)
  153.     {
  154.         int u, v;
  155.         cin >> u >> v;
  156.         cout << get(u, v) << endl;
  157.     }
  158. }
  159.  
  160. signed main()
  161. {
  162.     ios_base::sync_with_stdio(0);
  163.     cin.tie(0); cout.tie(0);
  164.  
  165.     int TC = 1;
  166.  
  167.     if(fopen(task".inp", "r"))
  168.     {
  169.         freopen(task".inp", "r", stdin);
  170.         freopen(task".out", "w", stdout);
  171.     }
  172.  
  173. //    if(fopen("note.inp", "r"))
  174. //    {
  175. //        freopen("note.inp", "r", stdin);
  176. //        freopen("note.out", "w", stdout);
  177. //    }
  178.  
  179.     while(TC--)
  180.     {
  181.         solve();
  182.         cout << endl;
  183.     }
  184.  
  185.     return 0;
  186. }
  187.  
Success #stdin #stdout 0.01s 11736KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/tfqD2v
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
3 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!