Submission #1174847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174847		achinhchin	Crocodile's Underground City (IOI11_crocodile)	C++17	0 / 100	1 ms	2628 KiB

crocodile

#include "crocodile.h"
#include <algorithm>
#include <vector>
#include <queue>
#include <utility> 
#include <climits>

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;
}

• Subtask 1: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11