이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
const int N = 1e5 + 69;
const int lg = 18;
int up[N][lg], mn[N][lg];
int tin[N], tout[N], timer, dep[N];
vector<pair<int, int>> g[N], t[N];
int n, m, k, cnt[N], d[N], q, p[N], sz[N];
vector<pair<int, int>> edges;
int find_set(int v) {
if (p[v] == v)
return v;
return p[v] = find_set(p[v]);
}
void unite(int a, int b) {
if (sz[a] < sz[b])
swap(a, b);
sz[a] += sz[b];
p[b] = a;
}
bool is_anc(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
void dfs(int v, int p) {
tin[v] = ++timer;
up[v][0] = p;
dep[v] = dep[p] + 1;
for (int i = 1;i < lg;i++) {
up[v][i] = up[up[v][i - 1]][i - 1];
mn[v][i] = min(mn[up[v][i - 1]][i - 1], mn[v][i - 1]);
}
for (auto u : t[v]) {
if (u.f == p)
continue;
mn[u.f][0] = u.s;
dfs(u.f, v);
}
tout[v] = timer;
}
int lca(int a, int b) {
if (is_anc(a, b))
return a;
else if (is_anc(b, a))
return b;
for (int i = lg - 1;i >= 0;i--) {
if (!is_anc(up[a][i], b) && up[a][i] > 0)
a = up[a][i];
}
return up[a][0];
}
int path(int a, int b) {
//b->lca
int dis = dep[a] - dep[b];
int res = 1e9;
for (int i = lg - 1;i >= 0;i--) {
if (dis >= (1 << i)) {
res = min(res, mn[a][i]);
a = up[a][i];
dis -= (1 << i);
}
}
return res;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt = 1;
//cin >> tt;
while (tt--) {
cin >> n >> m;
for (int i = 1;i <= m;i++) {
int a, b, w;
cin >> a >> b >> w;
g[a].push_back({b, w});
g[b].push_back({a, w});
edges.push_back({a ,b});
}
cin >> k;
for (int i = 1;i <= k;i++) {
int x;
cin >> x;
cnt[x] = 1;
}
cin >> q;
priority_queue<pair<int, int>> pq;
for (int i = 1;i <= n;i++) {
d[i] = 1e18;
p[i] = i, sz[i] = 1;
if (cnt[i]) {
pq.push({0, i});
d[i] = 0;
}
}
while (!pq.empty()) {
auto v = pq.top().s;
pq.pop();
for (auto u : g[v]) {
if (d[u.f] <= d[v] + u.s)
continue;
d[u.f] = d[v] + u.s;
pq.push({-d[u.f], u.f});
}
}
vector<tuple<int, int, int>> e;
for (auto u : edges) {
int a, b;
tie(a, b) = u;
int c = min(d[a], d[b]);
e.push_back({c, a, b});
}
sort(e.rbegin(), e.rend());
int sm = 0;
for (auto u : e) {
int a, b, c;
tie(c, a, b) = u;
int x = find_set(a);
int y = find_set(b);
if (x != y) {
sm += c;
t[a].push_back({b, c});
t[b].push_back({a, c});
unite(x, y);
}
}
dfs(1, 0);
while (q--) {
int s, t;
cin >> s >> t;
int lc = lca(s, t);
cout << min(path(s, lc), path(t, lc)) << '\n';
}
}
return 0;
}
# | 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... |