This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 1e5;
const int M = 1e18;
int n, m, k;
vector< pair<int, int> > g[N];
int AEC[N], distanc[N];
vector<int> A, B;
set< pair<int, int> > q;
void dijkstra(int start, vector<int>&dis){
for(int i = 0;i < n; i++) dis[i] = (i == start ? 0 : M);
q.insert({dis[start], start});
while(!q.empty()){
int v = q.begin()->ss;
q.erase(q.begin());
for(auto [to, len] : g[v]){
if(dis[to] > dis[v] + len){
q.erase({dis[to], to});
dis[to] = dis[v]+len;
q.insert({dis[to], to});
if(AEC[start]==0 and AEC[to] == 1){
distanc[start] = min(distanc[start], dis[to]);
}
if(AEC[start]==1 and AEC[to] == 0){
distanc[to] = min(distanc[to], dis[to]);
}
}
}
}
}
int used[N];
int s, t, ans;
void dfs(int v){
used[v] = 1;
if(v == t){
int mn = M;
for(int i = 0;i < n; i++){
if(used[i] == 1){
if(AEC[i] == 1) mn = 0;
else
mn = min(mn, distanc[i]);
}
}
ans = max(ans, mn);
}
for(auto [to, len] : g[v]){
if(used[to] == 0){
dfs(to);
}
}
used[v] = 0;
}
main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 0;i < m; i++){
int a, b, w; cin >> a >> b >> w;
a--, b--;
g[a].push_back({b, w});
g[b].push_back({a, w});
}
vector<int> dis(n);
cin >> k;
for(int i = 0;i < k; i++){
int a; cin >> a; a--;
AEC[a] = 1;
}
for(int i = 0;i < n; i++){
distanc[i] = M;
if(AEC[i] == 0) B.push_back(i);
else A.push_back(i);
}
if(k > (int)sqrt(n)){
for(int start : B){
dijkstra(start, dis);
}
}else{
for(int start : A){
dijkstra(start, dis);
}
}
int Q; cin >> Q;
while(Q--){
int a, b; cin >> a >> b; a--, b--;
if(AEC[a] == 1 or AEC[b] == 1){
cout << 0 << '\n';
}else{
if(n <= 15 and m <= 200){
s = a, t = b, ans = -M;
for(int i = 0;i < n; i++) used[i] = 0;
dfs(a);
cout << ans << '\n';
}else{
cout << min(distanc[a], distanc[b]) << '\n';
}
}
}
return 0;
}
Compilation message (stderr)
plan.cpp: In function 'void dijkstra(long long int, std::vector<long long int>&)':
plan.cpp:23:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
23 | for(auto [to, len] : g[v]){
| ^
plan.cpp: In function 'void dfs(long long int)':
plan.cpp:55:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
55 | for(auto [to, len] : g[v]){
| ^
plan.cpp: At global scope:
plan.cpp:63:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
63 | main(){
| ^~~~
# | 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... |