# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
421200 | OttoTheDino | Crocodile's Underground City (IOI11_crocodile) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,e) for (ll i = s; i <= e; ++i)
#define rrep(i,s,e) for (ll i = s; i >= e; --i)
#define pb push_back
#define pf push_front
#define fi first
#define se second
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
ll travel_plan (ll n, ll m, ll r[][2], ll l[], ll k, ll p[]) {
vii neibs[n];
rep (i,0,m-1) {
neibs[r[i][0]].pb({r[i][1], l[i]});
neibs[r[i][1]].pb({r[i][0], l[i]});
}
multiset<ll> doors[n];
bool done[n]={};
priority_queue<ii, vii, greater<ii>> pq;
rep (i,0,k-1) pq.push({0, p[i]});
while (!pq.empty()) {
ll dist = pq.top().fi, u = pq.top().se;
pq.pop();
if (done[u]) continue;
if (u==0) return dist;
for (ii vd : neibs[u]) {
ll v = vd.fi, d = vd.se;
doors[v].insert(d+dist);
if ((ll)doors[v].size()>1) pq.push({*(++doors[v].begin()), v});
}
done[u]=1;
}
assert(0==1);
return -1;
}