Submission #103738

#	Time	Username	Problem	Language	Result	Execution time	Memory
103738		wxh010910	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	819 ms	66672 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"

using namespace std;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  vector<vector<pair<int, int>>> adj(N);
  for (int i = 0; i < M; ++i) {
    adj[R[i][0]].emplace_back(R[i][1], L[i]);
    adj[R[i][1]].emplace_back(R[i][0], L[i]);
  }
  priority_queue<pair<int, int>> q;
  vector<bool> foo(N), bar(N);
  for (int i = 0; i < K; ++i) {
    foo[P[i]] = true;
    q.emplace(0, P[i]);
  }
  while (!q.empty()) {
    int x = q.top().second, d = -q.top().first;
    q.pop();
    if (!foo[x]) {
      foo[x] = true;
      continue;
    }
    if (!bar[x]) {
      bar[x] = true;
      if (!x) {
        return d;
      }
      for (auto p : adj[x]) {
        int y = p.first, w = p.second;
        if (!bar[y]) {
          q.emplace(-(d + w), y);
        }
      }
    }
  }
  return -1;
}

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