#include<bits/stdc++.h>
#define ll long long
const int MAXN=100000;
const ll INF=10000000000;
using namespace std;
vector < vector < ll > > dp(MAXN+5), dp_mn(MAXN+5);
vector < vector < pair < int, int > > > g(MAXN+5), tree(MAXN+5);
int time_in[MAXN+5], time_out[MAXN+5], parent[MAXN+5], pat[MAXN+5];
int n, m, timer, lg, rad, a, b;
vector < ll > dist;
set < pair < int, pair < int, int > > > stk;
set < pair < int, pair < int, int > > > ::iterator stk_it;
void make_set (int);
int find_set(int);
void union_sets(int,int);
void DFS (int,int,int);
int get_min(int,int);
int lca (int,int);
void sol();
bool issubtree (int a, int b) {
if (time_in[a]<=time_in[b] && time_out[b]<=time_out[a])
return true;
return false;
}
int main () {
scanf ("%d%d", &n, &m);
for (int k=1; k<=m; k++) {
int x, y, z;
scanf ("%d%d%d", &x, &y, &z);
g[x].push_back({y,z});
g[y].push_back({x,z});
}
dist.resize(n+1,INF);
set < pair < int, int > > st;
scanf ("%d", &rad);
for (int k=1; k<=rad; k++) {
int x;
scanf ("%d", &x);
dist[x]=0;
st.insert({dist[x],x});
}
while (!st.empty()) {
int v=(*st.begin()).second;
st.erase(st.begin());
for (int k=0; k<g[v].size(); k++) {
int to=g[v][k].first; int 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 (int k=1; k<=n; k++)
make_set(k);
for (int k=1; k<=n; k++)
for (int i=0; i<g[k].size(); i++) {
int x=k; int 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);
}
int lg=log2(n+1);
for (int k=0; k<=n; k++) {
dp[k].resize(lg+1);
dp_mn[k].resize(lg+1);
}
DFS(1,0,INF);
int Q;
scanf ("%d", &Q);
while (Q--)
sol();
return 0;
}
void sol() {
int a, b;
scanf ("%d%d", &a, &b);
int LCA=lca(a,b);
int answer=min(get_min(a,LCA),get_min(b,LCA));
printf ("%d\n", answer);
}
void make_set (int v) {
parent[v]=v;
}
int find_set (int v) {
if (v==parent[v])
return parent[v];
return parent[v]=find_set(parent[v]);
}
void union_sets (int a, int b) {
a=find_set(a);
b=find_set(b);
if (a!=b)
parent[b]=a;
}
void DFS (int v, int p, int d) {
pat[v]=p;
dp[v][0]=p;
dp_mn[v][0]=d;
for (int 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 (int k=0; k<tree[v].size(); k++) {
int to=tree[v][k].first;
if (to==p) continue;
DFS(to,v,tree[v][k].second);
}
time_out[v]=timer++;
}
int lca (int a, int b) {
if (issubtree(a,b))
return a;
if (issubtree(b,a))
return b;
for (int 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];
}
int get_min (int a, int LCA) {
ll counter=INF;
for (int 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(int, 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:56:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k=0; k<g[v].size(); k++) {
~^~~~~~~~~~~~
plan.cpp:71:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<g[k].size(); i++) {
~^~~~~~~~~~~~
plan.cpp:105:19: warning: overflow in implicit constant conversion [-Woverflow]
DFS(1,0,INF);
^
plan.cpp: In function 'void DFS(int, int, int)':
plan.cpp:164:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k=0; k<tree[v].size(); k++) {
~^~~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:33:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d", &n, &m);
~~~~~~^~~~~~~~~~~~~~~~
plan.cpp:37:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d%d", &x, &y, &z);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:45:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &rad);
~~~~~~^~~~~~~~~~~~
plan.cpp:48:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &x);
~~~~~~^~~~~~~~~~
plan.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &Q);
~~~~~~^~~~~~~~~~
plan.cpp: In function 'void sol()':
plan.cpp:118:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d", &a, &b);
~~~~~~^~~~~~~~~~~~~~~~
| # |
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 |
10 ms |
9848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
842 ms |
53600 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 |
- |
