Submission #786882

#	Time	Username	Problem	Language	Result	Execution time	Memory
786882		jakobrs	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	356 ms	72964 KiB

crocodile

#include "crocodile.h"

#include <tuple>
#include <utility>
#include <iostream>
#include <queue>
#include <vector>

using i64 = int64_t;

struct Node {
  i64 dist;
  i64 index;

  bool operator<(const Node &rhs) const {
    return std::tie(rhs.dist, index) < std::tie(dist, rhs.index);
  }
};

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  std::vector<std::vector<std::pair<i64, i64>>> adj(N);
  for (i64 i = 0; i < M; i++) {
    adj[R[i][0]].push_back({R[i][1], L[i]});
    adj[R[i][1]].push_back({R[i][0], L[i]});
  }

  std::vector<i64> distances(N, 1e18);
  std::vector<i64> distances2(N, 1e18);
  std::priority_queue<Node> pq;
  for (i64 i = 0; i < K; i++) {
    distances[P[i]] = 0;
    distances2[P[i]] = 0;
    pq.push(Node{.dist = 0, .index = P[i]});
  }
  while (!pq.empty()) {
    auto [dist, index] = pq.top();
    pq.pop();

    if (dist > distances2[index])
      continue;
    if (index == 0)
      return dist;

    for (auto [x, d] : adj[index]) {
      i64 new_dist = dist + d;
      if (new_dist < distances[x]) {
        if (distances[x] < distances2[x]) {
          pq.push(Node{.dist = distances[x], .index = x});
        }
        distances2[x] = distances[x];
        distances[x] = new_dist;
      } else if (new_dist < distances2[x]) {
        distances2[x] = new_dist;

        pq.push(Node{.dist = new_dist, .index = x});
      }
    }
  }
  return 0;
}

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