Submission #1296316

#TimeUsernameProblemLanguageResultExecution timeMemory
1296316LIAEvacuation plan (IZhO18_plan)C++17
23 / 100
270 ms31904 KiB
//
// Created by liasa on 28/11/2025.
//
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lp(i, s, e) for (int i = s; i < e; ++i)
#define v vector

int k, n;
v<int> in;
v<ll> dist;
const ll inf = 1e18;
#define pll pair<ll, ll>
v<v<pll>> g;
void dij() {
  dist.resize(n, inf);
  priority_queue<pll, v<pll>, greater<pll>> pq;
  for (auto it : in) {
    pq.push({0,it});
    dist[it] = 0;
  }

  while (!pq.empty()) {
    auto [d, nd] = pq.top();
    pq.pop();
    for (auto [it, c] : g[nd]) {
      if (dist[it] > c + d) {
        dist[it] = c + d;
        pq.push({c + d, it});
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int m;
  cin >> n >> m;
  g.resize(n);

  lp(i, 0, m) {
    ll a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    g[a].push_back({b,c});
    g[b].push_back({a,c});
  }

  cin >> k;
  lp(i, 0, k) {
    ll a;
    cin >> a;
    in.push_back(a - 1);
  }

  dij();

  int q;
  cin >> q;
  while (q--) {
    ll a, b;
    cin >> a >> b;
    a--;
    b--;
    ll ans = min(dist[a], dist[b]);
    cout << ans << '\n';
  }
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...