| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1274080 | g4yuhg | 악어의 지하 도시 (IOI11_crocodile) | C++20 | 0 ms | 0 KiB |
#include"crocodile.h"
#include<bits/stdc++.h>
typedef long long ll;
#define endl '\n'
#define fi first
#define se second
#define pii pair<ll, ll>
#define N 500005
using namespace std;
const ll inf = 1e18;
ll n, m, k, ans;
bool is[N];
ll d[N][2];
vector<pii> adj[N];
void dij() {
priority_queue<pii, vector<pii>, greater<pii>> pq;
for (int i = 1; i <= n; i ++) {
for (int j = 0; j < 2; j ++) {
d[i][j] = inf;
}
}
for (int i = 1; i <= n; i ++) {
if (is[i] == 0) continue;
d[i][1] = 0;
d[i][0] = 0;
pq.push({d[i][1], i});
}
while (pq.size()) {
auto c = pq.top().fi;
auto u = pq.top().se;
//cout << c << " " << u - 1 << endl;
pq.pop();
if (c > d[u][1]) continue;
for (auto v : adj[u]) {
ll cost = c + v.se;
ll mx0 = d[v.fi][0], mx1 = d[v.fi][1];
if (cost <= mx0) {
mx1 = mx0;
mx0 = cost;
}
else if (cost < mx1) {
mx1 = cost;
}
if (mx1 < d[v.fi][1]) {
d[v.fi][1] = mx1;
pq.push({d[v.fi][1], v.fi});
}
d[v.fi][0] = min(d[v.fi][0], mx0);
d[v.fi][1] = min(d[v.fi][1], mx1);
}
}
}
void solve() {
ans = inf;
dij();
ans = d[1][1];
//cout << ans << endl;
}
void lam() {
cin >> n >> m >> k;
for (int i = 1; i <= m; i ++) {
ll u, v, w;
cin >> u >> v >> w;
u ++ ; v ++ ;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for (int i = 1; i <= k; i ++) {
ll u; cin >> u;
u ++ ;
is[u] = 1;
}
solve();
}
ll travel_plan(ll nn, ll mm, ll R[][2], ll L[], ll kk, ll P[]) {
n = nn;
m = mm;
k = kk;
for (int i = 0; i < mm; i ++) {
ll u = R[i][0], v = R[i][1], w = L[i];
u ++ ;
v ++ ;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for (int i = 0; i < kk; i ++) {
ll u = P[i] + 1;
is[u] = 1;
}
ans = inf;
solve();
return ans;
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cout.tie(0);
//lam();
}