이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <stack>
#include <queue>
#include <deque>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define show(a) cerr << #a <<" -> "<< a <<" "
//#define int ll
const int N = 1e5 + 5;
const int INF = 1e9 + 5;
int n, m, k, q;
vector <pii> g[N];
vector <int> new_gr[N];
set <pii> st;
int dist[N], up[N][18], pr[N], tin[N], tout[N], tiktak;
bool was[N];
void dijkstra() {
while(sz(st)) {
int v = st.begin() -> S;
st.erase(st.begin());
for(pii it : g[v]) {
int w = it.F;
int to = it.S;
if(dist[to] > dist[v] + w) {
st.erase(mkp(dist[to], to));
dist[to] = dist[v] + w;
st.insert(mkp(dist[to], to));
}
}
}
}
int get_par(int v) {
if(pr[v] == v) return v;
return get_par(pr[v]);
}
void dfs(int v, int pre) {
// cerr << pre <<' '<< v <<'\n';
tin[v] = ++tiktak;
up[v][0] = pre;
for(int i = 1; i <= 17; ++i) {
up[v][i] = up[up[v][i - 1]][i - 1];
}
for(int to : new_gr[v]) {
if(to != pre)
dfs(to, v);
}
tout[v] = ++tiktak;
}
bool upper(int a, int b) {
return (tin[a] <= tin[b] && tout[b] <= tout[a]);
}
int lca(int a, int b) {
if(upper(a, b)) return a;
if(upper(b, a)) return b;
for(int i = 17; i >= 0; --i) {
if(!upper(up[a][i], b)) {
a = up[a][i];
break;
}
}
return up[a][0];
}
int main () {
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
cin >> n >> m;
for(int i = 1; i <= m; ++i) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a].pb(mkp(c, b));
g[b].pb(mkp(c, a));
}
for(int i = 1; i <= n; ++i)
dist[i] = INF, pr[i] = i;
cin >> k;
for(int i = 1; i <= k; ++i) {
int b; scanf("%d", &b);
dist[b] = 0;
st.insert(mkp(0, b));
}
dijkstra();
vector <pii> vec;
for(int i = 1; i <= n; ++i) {
vec.pb(mkp(dist[i], i));
}
sort(all(vec));
reverse(all(vec));
for(int i = 0; i < sz(vec); ++i) {
int v = vec[i].S;
was[v] = 1;
for(pii it : g[v]) {
int to = it.S;
int par_to = get_par(to);
if(was[to] && v != par_to) {
pr[par_to] = v;
// show(v);
// show(to);
// cerr << '\n';
new_gr[v].pb(par_to);
new_gr[par_to].pb(v);
}
}
}
// lca preprocess
dfs(vec[n - 1].S, vec[n - 1].S);
cin >> q;
for(int it = 1; it <= q; ++it) {
int s, t; cin >> s >> t;
printf("%d\n", dist[lca(s, t)]);
}
return 0;
}
/*
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
5
1 6
5 3
4 8
5 8
1 5
*/
컴파일 시 표준 에러 (stderr) 메시지
plan.cpp: In function 'int main()':
plan.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:102:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int b; scanf("%d", &b);
~~~~~^~~~~~~~~~
# | 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... |