# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1174845 | achinhchin | Crocodile's Underground City (IOI11_crocodile) | C++17 | 0 ms | 0 KiB |
#include "crocodile.h"
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
#include <iostream>
using namespace std;
typedef long long ll;
#define f first
#define s second
vector<pair<ll, ll> > a[100000]; priority_queue<pair<ll, ll> > b; pair<ll, ll> d[100000]; ll t, mn = LONG_LONG_MAX, i, c[100000], ds;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
while (M--) a[R[M][0]].push_back(make_pair(L[M], R[M][1])), a[R[M][1]].push_back(make_pair(L[M], R[M][0]));
for (i = 1; i < N; i++) c[i] = LONG_LONG_MAX; b.push(make_pair(0, 0));
while (!b.empty()) {
t = b.top().s, b.pop(), ds = 0;
for (auto i: a[t]) if (c[t] + i.f < c[i.s]) d[ds++] = make_pair(c[t] + i.f, i.s);
sort(d, d + ds); for (i = 1; i < ds; i++) c[d[i].s] = d[i].f, b.push(d[i]);
}while (K--) mn = min(mn, c[P[K]]);
return mn;
}