#include<bits/stdc++.h>
#define ll long long
const ll MAXN=100000;
const ll INF=10000000000;
using namespace std;
vector < vector < ll > > dp(MAXN+5), dp_mn(MAXN+5);
vector < vector < pair < ll, ll > > > g(MAXN+5), tree(MAXN+5);
ll time_in[MAXN+5], time_out[MAXN+5], parent[MAXN+5], pat[MAXN+5];
ll n, m, timer, lg, rad, a, b;
vector < ll > dist;
set < pair < ll, pair < ll, ll > > > stk;
set < pair < ll, pair < ll, ll > > > ::iterator stk_it;
void make_set (ll);
ll find_set(ll);
void union_sets(ll,ll);
void DFS (ll,ll,ll);
ll get_min(ll,ll);
ll lca (ll,ll);
void sol();
bool issubtree (ll a, ll b) {
if (time_in[a]<=time_in[b] && time_out[b]<=time_out[a])
return true;
return false;
}
int main () {
ios_base::sync_with_stdio(false);
cin >> n >> m;
for (ll k=1; k<=m; k++) {
ll x, y, z;
cin >> x >> y >> z;
g[x].push_back({y,z});
g[y].push_back({x,z});
}
dist.resize(n+1,INF);
set < pair < ll, ll > > st;
cin >> rad;
for (ll k=1; k<=rad; k++) {
ll x;
cin >> x;
dist[x]=0;
st.insert({dist[x],x});
}
while (!st.empty()) {
ll v=(*st.begin()).second;
st.erase(st.begin());
for (ll k=0; k<g[v].size(); k++) {
ll to=g[v][k].first; ll price=g[v][k].second;
if (dist[to]>dist[v]+price) {
st.erase({dist[to],to});
dist[to]=dist[v]+price;
st.insert({dist[to],to});
}
}
}
for (ll k=1; k<=n; k++)
make_set(k);
for (ll k=1; k<=n; k++)
for (ll i=0; i<g[k].size(); i++) {
ll x=k; ll y=g[k][i].first;
g[k][i].second=min(dist[x],dist[y]);
stk.insert({-g[k][i].second,{x,y}});
}
while (!stk.empty()) {
stk_it=stk.begin();
a=stk_it->second.first;
b=stk_it->second.second;
while (find_set(a)==find_set(b)) {
stk.erase(stk_it);
if (stk.empty()) break;
stk_it=stk.begin();
a=stk_it->second.first;
b=stk_it->second.second;
}
if (stk.empty()) break;
union_sets(a,b);
int price=stk_it->first;
tree[a].push_back(make_pair(b,-price));
tree[b].push_back(make_pair(a,-price));
stk.erase(stk_it);
}
ll lg=log2(n+1);
for (ll k=0; k<=n; k++) {
dp[k].resize(lg+1);
dp_mn[k].resize(lg+1);
}
DFS(1ll,0ll,INF);
int Q;
cin >> Q;
while (Q--)
sol();
return 0;
}
void sol() {
int a, b;
cin >> a >> b;
int LCA=lca(a,b);
ll answer=min(get_min(a,LCA),get_min(b,LCA));
cout << answer << endl;
}
void make_set (ll v) {
parent[v]=v;
}
ll find_set (ll v) {
if (v==parent[v])
return parent[v];
return parent[v]=find_set(parent[v]);
}
void union_sets (ll a, ll b) {
a=find_set(a);
b=find_set(b);
if (a!=b)
parent[b]=a;
}
void DFS (ll v, ll p, ll d) {
pat[v]=p;
dp[v][0]=p;
dp_mn[v][0]=d;
for (ll k=1; k<=lg; k++) {
dp[v][k]=dp[dp[v][k-1]][k-1];
if (dp[v][k]!=0)
dp_mn[v][k]=min(dp_mn[v][k-1],dp_mn[dp[v][k-1]][k-1]);
}
time_in[v]=timer++;
for (ll k=0; k<tree[v].size(); k++) {
ll to=tree[v][k].first;
if (to==p) continue;
DFS(to,v,tree[v][k].second);
}
time_out[v]=timer++;
}
ll lca (ll a, ll b) {
if (issubtree(a,b))
return a;
if (issubtree(b,a))
return b;
for (ll k=lg; k>=0; k--) {
if (dp[a][k]==0) continue;
if (issubtree(dp[a][k],b)) continue;
a=dp[a][k];
}
return pat[a];
}
ll get_min (ll a, ll LCA) {
ll counter=INF;
for (ll k=lg; k>=0; k--) {
if (dp[a][k]==0) continue;
if (issubtree(dp[a][k],LCA) && dp[a][k]!=LCA) continue;
counter=min(counter,dp_mn[a][k]);
a=dp[a][k];
}
return counter;
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
*/
Compilation message
plan.cpp: In function 'bool issubtree(long long int, long long int)':
plan.cpp:24:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if (time_in[a]<=time_in[b] && time_out[b]<=time_out[a])
^~
plan.cpp:27:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
return false;
^~~~~~
plan.cpp: In function 'int main()':
plan.cpp:57:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (ll k=0; k<g[v].size(); k++) {
~^~~~~~~~~~~~
plan.cpp:72:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (ll i=0; i<g[k].size(); i++) {
~^~~~~~~~~~~~
plan.cpp: In function 'void DFS(long long int, long long int, long long int)':
plan.cpp:165:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (ll k=0; k<tree[v].size(); k++) {
~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
880 ms |
60060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
