#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int mxN = 1e5 + 5 , mxLogDepth = 20 , limDepth=17;
int n,m,n_npp;
vector<pii> g[mxN];
vector<pii> adj;
bool npp[mxN];
// dijkstra npp
int dis[mxN];
// build new graph
struct EDGE
{
int u,v,w;
bool operator < (const EDGE &edge2) const{
return w < edge2.w;
}
};
vector<pii> tree[mxN];
int dsu[mxN];
// lca
int depth[mxN];
int ancestor[mxN][mxLogDepth];
int dp[mxN][mxLogDepth];
void dijkstra_npp(){
for(int i=0;i<mxN;i++) dis[i] = INT_MAX;
priority_queue<pii , vector<pii> , greater<pii>> pq;
for(int i=1;i<=n;i++){
if(npp[i]){
dis[i] = 0;
pq.push({dis[i] , i});
}
}
while(!pq.empty()){
auto [w , u] = pq.top();
pq.pop();
if(dis[u] < w) continue;
for(auto [v , ww] : g[u]){
if(dis[v] > w + ww){
dis[v] = w + ww;
pq.push({dis[v] , v});
}
}
}
}
int fp(int x){
if(dsu[x] == x) return x;
return dsu[x] = fp(dsu[x]);
}
void build_newGraph(){
priority_queue<EDGE> pq;
for(auto [u , v] : adj){
pq.push({u , v , min(dis[u] , dis[v])});
}
for(int i=1;i<=n;i++) dsu[i] = i;
while(!pq.empty()){
auto [u,v,w] = pq.top();
pq.pop();
int pa_u = fp(u) , pa_v = fp(v);
if(pa_u == pa_v) continue;
tree[u].push_back({v , w});
tree[v].push_back({u , w});
dsu[pa_v] = pa_u;
// printf("%d %d %d\n",u,v,w);
}
}
void dfs(int u , int pa){
for(auto [v , w] : tree[u]){
if(v == pa) continue;
depth[v] = depth[u] + 1;
ancestor[v][0] = u;
dp[v][0] = w;
dfs(v , u);
}
}
void k_ancestor(){
for(int k=1;k<=limDepth;k++){
for(int node=1;node<=n;node++){
ancestor[node][k] = ancestor[ancestor[node][k-1]][k-1];
dp[node][k] = min(dp[node][k-1] , dp[ancestor[node][k-1]][k-1]);
}
}
}
void pre_LCA(){
for(int i=0;i<mxN;i++) depth[i]=-1 , ancestor[i][0] = 0;
depth[1] = 1;
dfs(1 , -1);
// for(int i=1;i<=n;i++) printf("%d ",depth[i]);
// printf("\n");
k_ancestor();
// printf("\n");
// for(int k=0;k<4;k++) printf("%d %d\n" , ancestor[2][k] , dp[2][k]);
}
void LCA(int u , int v){
if(depth[u] > depth[v]){
LCA(v , u);
return ;
}
// printf("start (%d , %d) | (%d , %d)\n",u,depth[u],v,depth[v]);
int diff = depth[v] - depth[u];
int ans = min(dis[u] , dis[v]);
for(int i=0;i<=limDepth;i++){
if((1<<i) & diff){
ans = min(ans , dp[v][i]);
v = ancestor[v][i];
}
}
// printf("after lift v : (%d %d) (%d %d)\n",u,depth[u],v,depth[v]);
if(u == v){
printf("%d\n",ans);
return ;
}
for(int k=limDepth;k>=0;k--){
if(ancestor[u][k] == ancestor[v][k]){
ans = min({ans , dp[u][k] , dp[v][k]});
u = dp[u][k];
v = dp[v][k];
}
}
ans = min(ans , dp[u][0]);
printf("%d\n",ans);
}
int main(){
scanf("%d %d" ,&n ,&m);
for(int i=0;i<m;i++){
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
g[u].push_back({v,w});
g[v].push_back({u,w});
adj.push_back({u,v});
}
scanf("%d",&n_npp);
for(int i=0;i<mxN;i++) npp[i] = false;
for(int i=0;i<n_npp;i++){
int node;
scanf("%d",&node);
npp[node] = true;
}
dijkstra_npp();
// printf("dis : ");
// for(int i=1;i<=n;i++) printf("%d ",dis[i]);
// printf("\n\n");
build_newGraph();
pre_LCA();
int q;
scanf("%d",&q);
while(q--){
int u,v;
scanf("%d %d",&u,&v);
LCA(u,v);
}
return 0;
}
Compilation message
plan.cpp: In function 'void dijkstra_npp()':
plan.cpp:45:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
45 | auto [w , u] = pq.top();
| ^
plan.cpp:50:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
50 | for(auto [v , ww] : g[u]){
| ^
plan.cpp: In function 'void build_newGraph()':
plan.cpp:67:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
67 | for(auto [u , v] : adj){
| ^
plan.cpp:74:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
74 | auto [u,v,w] = pq.top();
| ^
plan.cpp: In function 'void dfs(int, int)':
plan.cpp:90:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
90 | for(auto [v , w] : tree[u]){
| ^
plan.cpp: In function 'int main()':
plan.cpp:166:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
166 | scanf("%d %d" ,&n ,&m);
| ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:170:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
170 | scanf("%d %d %d",&u,&v,&w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
plan.cpp:176:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
176 | scanf("%d",&n_npp);
| ~~~~~^~~~~~~~~~~~~
plan.cpp:181:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
181 | scanf("%d",&node);
| ~~~~~^~~~~~~~~~~~
plan.cpp:196:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
196 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
plan.cpp:200:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
200 | scanf("%d %d",&u,&v);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
15708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
15708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
15708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
193 ms |
36076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
15708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
