이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int LOG = 17;
const int INF = 1000000000;
struct unionfind{
vector<int> p;
unionfind(int N): p(N, -1){
}
int root(int x){
if (p[x] < 0){
return x;
} else {
p[x] = root(p[x]);
return p[x];
}
}
bool same(int x, int y){
return root(x) == root(y);
}
void unite(int x, int y){
x = root(x);
y = root(y);
if (x != y){
if (p[x] < p[y]){
swap(x, y);
}
p[y] += p[x];
p[x] = y;
}
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> E(n);
for (int i = 0; i < m; i++){
int a, b, w;
cin >> a >> b >> w;
a--;
b--;
E[a].push_back(make_pair(w, b));
E[b].push_back(make_pair(w, a));
}
int k;
cin >> k;
vector<int> g(k);
for (int i = 0; i < k; i++){
cin >> g[i];
g[i]--;
}
vector<int> d(n, -1);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for (int i = 0; i < k; i++){
pq.push(make_pair(0, g[i]));
}
while (!pq.empty()){
int c = pq.top().first;
int v = pq.top().second;
pq.pop();
if (d[v] == -1){
d[v] = c;
for (auto P : E[v]){
int w = P.second;
if (d[w] == -1){
pq.push(make_pair(c + P.first, w));
}
}
}
}
vector<tuple<int, int, int>> E2;
for (int i = 0; i < n; i++){
for (auto P : E[i]){
int j = P.second;
if (i < j){
E2.push_back(make_tuple(min(d[i], d[j]), i, j));
}
}
}
sort(E2.begin(), E2.end(), greater<tuple<int, int, int>>());
unionfind UF(n);
vector<vector<pair<int, int>>> E3(n);
for (int i = 0; i < m; i++){
int u = get<1>(E2[i]);
int v = get<2>(E2[i]);
if (!UF.same(u, v)){
UF.unite(u, v);
int c = get<0>(E2[i]);
E3[u].push_back(make_pair(c, v));
E3[v].push_back(make_pair(c, u));
}
}
vector<int> p(n, -1);
vector<int> a(n);
vector<vector<int>> c(n);
vector<int> d2(n, 0);
queue<int> q;
q.push(0);
while (!q.empty()){
int v = q.front();
q.pop();
for (auto P : E3[v]){
int w = P.second;
if (w != p[v]){
p[w] = v;
a[w] = P.first;
c[v].push_back(w);
d2[w] = d2[v] + 1;
q.push(w);
}
}
}
vector<vector<int>> pp(LOG, vector<int>(n, -1));
vector<vector<int>> mn(LOG, vector<int>(n, INF));
for (int i = 0; i < n; i++){
pp[0][i] = p[i];
mn[0][i] = a[i];
}
for (int i = 0; i < LOG - 1; i++){
for (int j = 0; j < n; j++){
if (pp[i][j] != -1){
pp[i + 1][j] = pp[i][pp[i][j]];
if (pp[i + 1][j] != -1){
mn[i + 1][j] = min(mn[i][j], mn[i][pp[i][j]]);
}
}
}
}
int Q;
cin >> Q;
for (int i = 0; i < Q; i++){
int s, t;
cin >> s >> t;
s--;
t--;
int ans = INF;
if (d2[s] > d2[t]){
swap(s, t);
}
for (int j = 0; j < LOG; j++){
if (((d2[t] - d2[s]) >> j & 1) == 1){
ans = min(ans, mn[j][t]);
t = pp[j][t];
}
}
if (s != t){
for (int j = LOG - 1; j >= 0; j--){
if (pp[j][s] != pp[j][t]){
ans = min(ans, mn[j][s]);
ans = min(ans, mn[j][t]);
s = pp[j][s];
t = pp[j][t];
}
}
ans = min(ans, mn[0][s]);
ans = min(ans, mn[0][t]);
}
cout << ans << endl;
}
}
# | 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... |