#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
using pli = pair<ll,int>;
const int N = 1e5 + 5, M = 5e5 + 5;
const ll inf = 1e18; // beaware maybe not enough
vector<pli> adj[N];
ll D[N], mn[N][20];
bool vis[N];
tuple<int,int,int> E[M];
tuple<ll,int,int> edges[M];
int p[N], up[N][20], dep[N], LOG, sz[N];
int fp(int x){if(x == p[x]) return x; return p[x] = fp(p[x]);}
void dfs(int u, int p, ll wp){
up[u][0] = p; mn[u][0] = min(mn[u][0], wp);
if(u != p) dep[u] = dep[p] + 1;
for(int j = 1; j<LOG; ++j){
up[u][j] = up[up[u][j-1]][j-1];
mn[u][j] = min(mn[u][j-1], mn[up[u][j-1]][j-1]);
}
for(pli it: adj[u]){
ll w = it.first; int v = it.second;
if(v != p) dfs(v, u, w);
}
}
pair<ll,int> get_lca(int u, int v){
ll w = inf;
if(u == v) return make_pair(w, u);
if(dep[u] < dep[v]) swap(u, v);
for(int j = LOG-1; j>=0; --j) if((dep[u]-dep[v])>>j&1) w = min(w, mn[u][j]), u = up[u][j];
if(u == v) return make_pair(w, u);
for(int j = LOG-1; j>=0; --j) if(up[u][j] != up[v][j]){w = min({w, mn[u][j], mn[v][j]}); u = up[u][j]; v = up[v][j];}
return make_pair(min(w, mn[u][0]), up[u][0]);
}
signed main(){
int n, m; scanf("%d %d", &n, &m); LOG = 32 - __builtin_clz(n);
for(int i = 0, u, v, w; i<m; ++i){
scanf("%d %d %d", &u, &v, &w); --u; --v;
E[i] = make_tuple(u, v, w);
adj[u].emplace_back(w, v); adj[v].emplace_back(w, u);
}
priority_queue<pli, vector<pli>, greater<pli>> pq;
fill(D, D+n, inf); fill(vis, vis+n, false);
int k; scanf("%d", &k);
for(int i = 0, u; i<k; ++i) scanf("%d", &u), pq.emplace(D[u-1] = 0, u-1);
while(!pq.empty()){
int u = pq.top().second; pq.pop();
if(vis[u]) continue; vis[u] = true;
for(pli it: adj[u]){
ll w = it.first; int v = it.second;
if(D[u] < inf && D[u] + w < D[v]) pq.emplace(D[v] = D[u] + w, v);
}
}
for(int i = 0; i<m; ++i){
int u, v, _; tie(u, v, _) = E[i];
edges[i] = make_tuple(min(D[u], D[v]), u, v);
}
for(int i = 0; i<n; ++i){
adj[i].clear(); p[i] = i; sz[i] = 1; fill(mn[i], mn[i]+LOG, inf);
}
sort(edges, edges+m, greater<tuple<ll,int,int>>());
for(int i = 0; i<m; ++i){
ll w; int u, v; tie(w, u, v) = edges[i];
if(fp(u) != fp(v)){
int pu = fp(u), pv = fp(v);
if(sz[pu] < sz[pv]) swap(pu, pv);
sz[pu] += sz[pv]; p[pv] = pu;
adj[u].emplace_back(w, v); adj[v].emplace_back(w, u);
}
}
dfs(0, 0, inf);
int q; scanf("%d", &q);
while(q--){
int u, v; scanf("%d %d", &u, &v); --u; --v;
pair<ll,int> tmp = get_lca(u, v);
ll w = tmp.first; int lca = tmp.second;
printf("%lld\n", w);
}
}
Compilation message
plan.cpp: In function 'int main()':
plan.cpp:48:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
48 | if(vis[u]) continue; vis[u] = true;
| ^~
plan.cpp:48:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
48 | if(vis[u]) continue; vis[u] = true;
| ^~~
plan.cpp:76:25: warning: unused variable 'lca' [-Wunused-variable]
76 | ll w = tmp.first; int lca = tmp.second;
| ^~~
plan.cpp:36:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | int n, m; scanf("%d %d", &n, &m); LOG = 32 - __builtin_clz(n);
| ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | scanf("%d %d %d", &u, &v, &w); --u; --v;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
44 | int k; scanf("%d", &k);
| ~~~~~^~~~~~~~~~
plan.cpp:45:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | for(int i = 0, u; i<k; ++i) scanf("%d", &u), pq.emplace(D[u-1] = 0, u-1);
| ~~~~~^~~~~~~~~~
plan.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | int q; scanf("%d", &q);
| ~~~~~^~~~~~~~~~
plan.cpp:74:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | int u, v; scanf("%d %d", &u, &v); --u; --v;
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
14936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
205 ms |
49804 KB |
Output is correct |
| 2 |
Correct |
352 ms |
70104 KB |
Output is correct |
| 3 |
Correct |
359 ms |
70040 KB |
Output is correct |
| 4 |
Correct |
91 ms |
43360 KB |
Output is correct |
| 5 |
Correct |
343 ms |
70088 KB |
Output is correct |
| 6 |
Correct |
365 ms |
70076 KB |
Output is correct |
| 7 |
Correct |
343 ms |
70052 KB |
Output is correct |
| 8 |
Correct |
371 ms |
69992 KB |
Output is correct |
| 9 |
Correct |
348 ms |
70080 KB |
Output is correct |
| 10 |
Correct |
352 ms |
69932 KB |
Output is correct |
| 11 |
Correct |
345 ms |
70012 KB |
Output is correct |
| 12 |
Correct |
358 ms |
70212 KB |
Output is correct |
| 13 |
Correct |
359 ms |
70088 KB |
Output is correct |
| 14 |
Correct |
353 ms |
70052 KB |
Output is correct |
| 15 |
Correct |
347 ms |
71852 KB |
Output is correct |
| 16 |
Correct |
366 ms |
70088 KB |
Output is correct |
| 17 |
Correct |
345 ms |
70136 KB |
Output is correct |
| 18 |
Correct |
350 ms |
70156 KB |
Output is correct |
| 19 |
Correct |
83 ms |
44980 KB |
Output is correct |
| 20 |
Correct |
356 ms |
70080 KB |
Output is correct |
| 21 |
Correct |
339 ms |
69384 KB |
Output is correct |
| 22 |
Correct |
71 ms |
42228 KB |
Output is correct |
| 23 |
Correct |
87 ms |
41312 KB |
Output is correct |
| 24 |
Correct |
74 ms |
42044 KB |
Output is correct |
| 25 |
Correct |
73 ms |
42020 KB |
Output is correct |
| 26 |
Correct |
93 ms |
41944 KB |
Output is correct |
| 27 |
Correct |
92 ms |
44720 KB |
Output is correct |
| 28 |
Correct |
77 ms |
42048 KB |
Output is correct |
| 29 |
Correct |
99 ms |
43924 KB |
Output is correct |
| 30 |
Correct |
73 ms |
42092 KB |
Output is correct |
| 31 |
Correct |
92 ms |
44136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
