Submission #483918

#	Time	Username	Problem	Language	Result	Execution time	Memory
483918		evenvalue	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	479 ms	73096 KiB

crocodile

#include "crocodile.h"
#include <queue>
#include <vector>
using namespace std;

struct edge {
  int x;
  int y;
  int w;
};

class solution {
  const int kInf = 1e9 + 10;
  const int n;
  const int m;
  const vector<edge> edges;
  const int k;
  const vector<int> end;
  vector<vector<pair<int, int>>> g;
  vector<int> dp_mn, dp_mn2;

  void dijkstra() {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
    for (const int x : end) {
      q.push(make_pair(0, x));
      dp_mn[x] = dp_mn2[x] = 0;
    }
    while (not q.empty()) {
      const auto [d, x] = q.top();
      q.pop();
      if (dp_mn2[x] < d) continue;
      for (const auto &[y, w] : g[x]) {
        int cur = d + w;
        if (cur < dp_mn[y]) {
          swap(dp_mn[y], cur);
        }
        if (cur < dp_mn2[y]) {
          dp_mn2[y] = cur;
          q.push(make_pair(dp_mn2[y], y));
        }
      }
    }
  }

public:
  explicit solution(const int n, const vector<edge> &edges, const vector<int> &end)
      : n(n), m(edges.size()), edges(edges), k(end.size()), end(end), g(n), dp_mn(n, kInf), dp_mn2(n, kInf) {
    for (const auto &[x, y, w] : edges) {
      g[x].emplace_back(y, w);
      g[y].emplace_back(x, w);
    }
  }

  int solve() {
    dijkstra();
    return dp_mn2[0];
  }
};

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  vector<edge> edges(M);
  for (int i = 0; i < M; i++) {
    edges[i].x = R[i][0];
    edges[i].y = R[i][1];
    edges[i].w = L[i];
  }
  vector<int> end(K);
  for (int i = 0; i < K; i++) {
    end[i] = P[i];
  }
  solution s(N, edges, end);
  return s.solve();
}

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