Submission #1077159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077159		juicy	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	637 ms	75440 KiB

crocodile

#include "crocodile.h"

#include <bits/stdc++.h>

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]) {
  std::vector<std::vector<std::array<int, 2>>> g(n);
  for (int i = 0; i < m; ++i) {
    g[R[i][0]].push_back({R[i][1], L[i]});
    g[R[i][1]].push_back({R[i][0], L[i]});
  }
  std::vector<int> d(n), vis(n);
  std::priority_queue<std::array<int, 2>, std::vector<std::array<int, 2>>, std::greater<std::array<int, 2>>> pq;
  for (int i = 0; i < k; ++i) {
    int u = P[i];
    vis[u] = 1;
    pq.push({0, u});
  }
  while (pq.size()) {
    auto [c, u] = pq.top(); pq.pop();
    if (vis[u] == 2) {
      continue;
    }
    if (++vis[u] == 2) {
      d[u] = c;
      for (auto [v, w] : g[u]) {
        pq.push({c + w, v});
      }
    }
  }
  return d[0];
}

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