#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5;
//dsu rollback + parallel binary search
struct DSU{
vector<pair<int, int>> past_p, past_sz;
vector<int> st;
int p[maxn], sz[maxn];
void init(){
for(int i = 1; i < maxn; i++){
p[i] = i;
sz[i] = 1;
}
}
int find(int u){
return (p[u] == u ? u : find(p[u]));
}
void unon(int a, int b){
a = find(a);
b = find(b);
if(sz[a] < sz[b]) swap(a, b);
past_sz.push_back({a, sz[a]});
past_p.push_back({b, p[b]});
if(a != b){
sz[a] += sz[b];
p[b] = a;
}
}
void rollback(){
}
void save(){
st.push_back(past_p.size());
}
void to_last(){
while(past_p.size() != st.back()){
p[past_p.back().first] = past_p.back().second;
sz[past_sz.back().first] = past_sz.back().second;
past_p.pop_back();
past_sz.pop_back();
}
st.pop_back();
}
} dsu;
int ans[maxn], s[maxn], t[maxn], pos[maxn];
vector<pair<int, int>> adj[maxn];
vector<int> comp, all;
void solve(int l, int r, vector<int>& cur){
if(l == r) for(int i: cur) ans[i] = l;
else{
dsu.save();
int mid = (l + r) / 2;
for(int i = l; i <= mid; i++){
for(auto [v, w]: adj[comp[i]]){
if(pos[v] <= mid) dsu.unon(comp[i], v);
}
}
vector<int> le, ri;
for(int i: cur){
if(dsu.find(s[i]) == dsu.find(t[i])) le.push_back(i);
else ri.push_back(i);
}
if(mid < r && ri.size()) solve(mid + 1, r, ri);
dsu.to_last();
if(le.size()) solve(l, mid, le);
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m; cin >> n >> m;
vector<int> d(n + 1, 1e9);
for(int i = 1; i <= m; i++){
int u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
int k; cin >> k;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for(int i = 0; i < k; i++){
int x; cin >> x;
d[x] = 0;
pq.push({0, x});
}
while(!pq.empty()){
auto [curw, u] = pq.top();
pq.pop();
if(d[u] != curw) continue;
for(auto [v, w]: adj[u]){
if(d[v] > curw + w){
d[v] = curw + w;
pq.push({d[v], v});
}
}
}
for(int i = 1; i <= n; i++) comp.push_back(i);
sort(comp.begin(), comp.end(), [&](int x, int y){
return d[x] > d[y];
});
int q; cin >> q;
for(int i = 0; i < q; i++){
cin >> s[i] >> t[i];
all.push_back(i);
}
for(int i = 0; i < n; i++) pos[comp[i]] = i;
dsu.init();
solve(0, n - 1, all);
for(int i = 0; i < q; i++) cout << d[comp[ans[i]]] << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |