fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define all(dataStructure) dataStructure.begin(),dataStructure.end()
  3. #define ll long long
  4.  
  5. using namespace std;
  6. namespace std {
  7.         template <typename T, int D>
  8.         struct _vector : public vector <_vector <T, D - 1>> {
  9.                 static_assert(D >= 1, "Dimension must be positive!");
  10.                 template <typename... Args>
  11.                 _vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
  12.         };
  13.         // _vector <int, 3> a(n, m, k);: int a[n][m][k].
  14.         // _vector <int, 3> a(n, m, k, x);: int a[n][m][k] initialized with x.
  15.         template <typename T>
  16.         struct _vector <T, 1> : public vector <T> {
  17.                 _vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
  18.         };
  19. }
  20.  
  21. const int MAX = 1e5 + 3;
  22. const ll MOD[] = {1000000007, 998244353};
  23.  
  24. int n, m, k, q;
  25. ll dp[MAX];
  26. ll ans[MAX], L[MAX], R[MAX];
  27. vector <pair <int, int>> adj[MAX];
  28. priority_queue <pair <ll, int>> pq;
  29. int u[MAX], v[MAX];
  30.  
  31. void dijkstra() {
  32.         while (pq.size()) {
  33.                 auto [D, u] = pq.top();
  34.                 pq.pop();
  35.                 D = -D;
  36.                 if (D != dp[u]) continue;
  37.                 for (auto &[v, c] : adj[u]) {
  38.                         if (dp[v] > dp[u] + c) {
  39.                                 dp[v] = dp[u] + c;
  40.                                 pq.emplace(-dp[v], v);
  41.                         }
  42.                 }
  43.         }
  44. }
  45.  
  46. vector <ll> disDist;
  47. vector <pair <int, int>> edges[MAX];
  48. vector <int> queriesAt[MAX];
  49. int pa[MAX];
  50.  
  51. int findpa(int u) {
  52.         return u == pa[u] ? u : pa[u] = findpa(pa[u]);
  53. }
  54.  
  55. void join(int u, int v) {
  56.         u = findpa(u);
  57.         v = findpa(v);
  58.         pa[v] = u;
  59. }
  60.  
  61. template <typename dataType>
  62. inline void compress(vector <dataType> &x) {
  63.         sort(all(x));
  64.         x.erase(unique(all(x)), x.end());
  65. }
  66.  
  67. void init() {
  68.         for (int u = 1; u <= n; u++) disDist.push_back(dp[u]);
  69.         compress(disDist);
  70.  
  71.         for (int i = 0; i < q; i++) {
  72.                 L[i] = 0, R[i] = (int)disDist.size() - 1;
  73.         }
  74.  
  75.         for (int u = 1; u <= n; u++) {
  76.                 for (auto &[v, c] : adj[u]) if (u < v) {
  77.                         int id = lower_bound(all(disDist), min(dp[u], dp[v])) - disDist.begin();
  78.                         edges[id].emplace_back(u, v);
  79.                 }
  80.         }
  81. }
  82.  
  83. void Solve() {
  84.         cin >> n >> m >> k >> q;
  85.         memset(dp, 0x0f, sizeof dp);
  86.  
  87.         for (int i = 0; i < m; i++) {
  88.                 int u, v, c;
  89.                 cin >> u >> v >> c;
  90.                 adj[u].emplace_back(v, c);
  91.                 adj[v].emplace_back(u, c);
  92.         }
  93.  
  94.         for (int i = 0; i < k; i++) {
  95.                 int x;
  96.                 cin >> x;
  97.                 dp[x] = 0;
  98.                 pq.emplace(0ll, x);
  99.         }
  100.  
  101.         dijkstra();
  102.         init();
  103.  
  104.         for (int i = 0; i < q; i++) {
  105.                 cin >> u[i] >> v[i];
  106.         }
  107.  
  108.  
  109.         int itorateTime = 18;
  110.         while (itorateTime--) {
  111.                 iota(pa + 1, pa + n + 1, 1);
  112.                 for (int i = 0; i < q; i++) {
  113.                         if (L[i] <= R[i]) {
  114.                                 queriesAt[(L[i] + R[i]) / 2].push_back(i);
  115.                         }
  116.                 }
  117.                 for (int i = (int)disDist.size() - 1; i >= 0; i--) {
  118.                         for (auto &[u, v] : edges[i]) join(u, v);
  119.                         for (int &j : queriesAt[i]) {
  120.                                 if (findpa(u[j]) == findpa(v[j])) {
  121.                                         ans[j] = disDist[i];
  122.                                         L[j] = i + 1;
  123.                                 } else {
  124.                                         R[j] = i - 1;
  125.                                 }
  126.                         }
  127.                         queriesAt[i].clear();
  128.                 }
  129.         }
  130.  
  131.         for (int i = 0; i < q; i++) cout << ans[i] << '\n';
  132. }
  133.  
  134. int32_t main() {
  135.         ios_base::sync_with_stdio(0);
  136.         cin.tie(0);
  137.  
  138.         #define TASK "WALK"
  139.         if (fopen(TASK".INP", "r")) {
  140.                 freopen(TASK".INP", "r", stdin);
  141.                 freopen(TASK".OUT", "w", stdout);
  142.         }
  143.  
  144.         /* int TEST = 1; cin >> TEST; while (TEST--) */ Solve();
  145.  
  146.         cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  147.         return 0;
  148. }
  149.  
Success #stdin #stdout #stderr 0.01s 14100KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Time elapsed: 0.007044s
https://ideone.com/Hn6eJg
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!