| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 460719 | 2021-08-09T08:33:05 Z | fuad27 | 악어의 지하 도시 (IOI11_crocodile) | C++14 | 0 ms | 0 KB |
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define maxN 100005
#define INF 1e17
#define int long long
vector < pair < int, int >> adj[maxN];
vector < int > d(maxN, 0);
vector < int > ans(maxN, INF);
int solve(int src) {
d[src] = 1;
priority_queue < int > q;
for (pair < int, int > v: adj[src]) {
if (d[v.s] == 0) {
int x = solve(v.second);
if (q.size() < 2) {
q.push(v.f + x);
} else {
if (v.f + x < q.top()) {
q.pop();
q.push(v.f + x);
}
}
} else if (d[v.s] == 1) {
continue;
} else {
int x = ans[v.s];
if (q.size() < 2) {
q.push(v.f + x);
} else {
if (v.f + x < q.top()) {
q.pop();
q.push(v.f + x);
}
}
}
}
if (q.size() < 2) ans[src] = INF;
else ans[src] = q.top();
d[src] = 2;
return ans[src];
}
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
for (int i = 0; i < m; i++) {
int a = r[i][0], b = r[i][1], w = l[i];
adj[a].push_back({
w,
b
});
adj[b].push_back({
w,
a
});
}
for (int i = 0; i < k; i++) {
ans[p[i]] = 0;
d[p[i]] = 2;
}
return solve(0);
}