Submission #469720

#	Time	Username	Problem	Language	Result	Execution time	Memory
469720		Soumya1	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	600 ms	63156 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
  vector<pair<int, int>> ad[n];
  for (int i = 0; i < m; i++) {
    ad[r[i][0]].push_back({r[i][1], l[i]});
    ad[r[i][1]].push_back({r[i][0], l[i]});
  }
  vector<int> d1(n, 1e9 + 5);
  vector<int> d2(n, 1e9 + 5);
  priority_queue<pair<int, int>> pq;
  for (int i = 0; i < k; i++) {
    d1[p[i]] = d2[p[i]] = 0;
    pq.push({0, p[i]});
  }
  vector<bool> vis(n, false);
  while (!pq.empty()) {
    int u = pq.top().second;
    pq.pop();
    if (vis[u]) continue;
    vis[u] = true;
    for (auto [v, w] : ad[u]) {
      if (d1[v] >= d2[u] + w) {
        d2[v] = d1[v];
        d1[v] = d2[u] + w;
        pq.push({-d2[v], v});
      } else if (d2[v] > d2[u] + w) {
        d2[v] = d2[u] + w;
        pq.push({-d2[v], v});
      }
    }
  }
  return d2[0];
}

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