| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 860231 | 2023-10-12T09:23:21 Z | phongcd | Crocodile's Underground City (IOI11_crocodile) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ii pair <int, int>
#define ill pair <ll, ll>
#define ild pair <ld, ld>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define file "test"
using namespace std;
const int N = 1e5 + 2;
const int M = 10;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const ll base = 311;
const int BLOCK_SIZE = 400;
int n, m, k;
vector <ill> g[N];
ll travel_plan (int nn, int mm, int r[][2], int l[], int kk, int p[]){
n = nn, mm = m, k = kk;
for (int i = 0; i < m; i ++) {
ll u = r[i][0], v = r[i][1], w = l[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
vector <ill> d(n);
for (int i = 0; i < n; i ++) d[i] = {INF, INF};
set <ill> h;
for (int i = 0, u; i < k; i ++) {
u = l[i];
h.insert({0, u});
d[u] = {0, 0};
}
vector <bool> p(n);
while (!h.empty()) {
int u = (*h.begin()).se;
ll dis = (*h.begin()).fi;
h.erase(h.begin());
if (p[u]) continue;
p[u] = 1;
for (ill e: g[u]) {
int v = e.fi; ll w = e.se;
if (d[v].fi > dis + w) {
d[v] = {dis + w, d[v].fi};
h.insert({d[v].se, v});
}
else if (d[v].se > dis + w) {
d[v].se = dis + w;
h.insert({d[v].se, v});
}
}
}
return d[0].se;
}
/*
/\_/\ zzZ
(= -_-)
/ >u >u
*/