| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 494318 | keertan | Crocodile's Underground City (IOI11_crocodile) | C++98 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
Always took the second best answer.
Let's call g2(A) is the second smallest number of an arbitrary set A.
Subtask 1:
f[node] = g2(f[c_i] + len(node, c_i))
Subtask 2:
Make a new data structure that support:
- Storing the two smallest number of the set
- Allowing update: add one new number to the set.
(don't need to store the whole set, just need the two smallest number)
f[exit node] = {0, 0}. f[others] = {oo, oo}
when poppin a node from pq:
- when processing a child C:
val = f[child]
val.add(f[node].p2 + len(node, child))
if better:
assign
if there are at least two choices in the set:
push to pq.
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 1000001
#define fi first
#define se second
#define FOR(type, i, a, b) for(type i = (a); i <= (b); i++)
#define FORD(type, i, b, a) for(type i = (b); i >= (a); i--)
//================================================================
const ll oo = 1e18;
struct Node
{
int node, len;
Node() {node = len = 0;}
Node(int node, int len) {this -> node = node, this -> len = len;}
};
typedef vector<Node> vg;
int n, m, k;
vector<Node> graph[MAX];
int exits[MAX];
bool isExit[MAX];
int checkSubtask(){
if (m == n - 1) return 1;
if (m <= 100000) return 2;
return 3;
}
//===========================================================
ll f1[MAX];
ll dfs1(int node, int parent){
ll &ans = f1[node];
if (isExit[node]) return ans = 0;
vector<ll> save;
for (Node ch: graph[node]){
int child = ch.node;
if (child == parent) continue;
ll tmp = dfs1(child, node);
if (tmp < oo)
save.push_back(tmp + ch.len);
}
if (save.size() < 2) return false;
sort(save.begin(), save.end());
return save[1];
}
void sub1(){
memset(f1, 0x3f, sizeof(f1));
cout << dfs1(0, 0);
}
//===========================================================
struct Best{
ll p1 = oo, p2 = oo;
Best(){
p1 = p2 = oo;
}
Best(int p1, int p2): p1(p1), p2(p2){}
bool ok(){
return p1 != oo and p2 != oo;
}
void add(int num){
if (num <= p1)
p2 = p1, p1 = num;
else if (num <= p2)
p2 = num;
}
};
bool operator < (Best a, Best b){
return (a.p2 != b.p2) ? (a.p2 < b.p2) : (a.p1 < b.p1);
}
bool operator > (Best a, Best b){
return (a.p2 != b.p2) ? (a.p2 > b.p2) : (a.p1 > b.p1);
}
bool operator == (Best a, Best b){
return a.p1 == b.p1 and a.p2 == b.p2;
}
bool operator != (Best a, Best b){
return not (a == b);
}
Best f[MAX];
typedef pair<Best, int> Data;
priority_queue<Data, vector<Data>, greater<Data>> pq;
void init(){
FOR(int, i, 0, n - 1)
if (isExit[i])
f[i] = {0, 0},
pq.push({f[i], i});
else
f[i] = Best();
}
void sub23(){
init();
while (!pq.empty()){
pair<Best, int> cur = pq.top(); pq.pop();
int node = cur.se; Best val = cur.fi;
if (val != f[node]) continue;
for (Node ch: graph[node]){
int child = ch.node;
int edgeVal = val.p2 + ch.len;
Best childVal = f[child]; childVal.add(edgeVal);
if (childVal < f[child]){
f[child] = childVal;
if (f[child].ok())
pq.push({f[child], child});
}
}
}
cout << f[0].p2;
}
//===========================================================
void input();
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
input();
int subtask = checkSubtask();
if (subtask == 1)
sub1();
else
sub23();
}
void input(){
cin >> n >> m >> k;
FOR(int, i, 1, m){
int u, v, l; cin >> u >> v >> l;
graph[u].push_back({v, l});
graph[v].push_back({u, l});
}
FOR(int, i, 0, k - 1){
int u; cin >> u;
exits[i] = u;
isExit[u] = true;
}
}