Submission #723473

#	Time	Username	Problem	Language	Result	Execution time	Memory
723473		yashsingh	Crocodile's Underground City (IOI11_crocodile)	C++17	0 / 100	1 ms	340 KiB

crocodile

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll travel_plan(int n, int m, int (*r) [2], int*l, int k, int*p) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  // multi-source (exit) dijkstra to find distance from any source to a exit
  // BFS out of the exits and calculate DP as 2nd min of any outgoing node

  priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;

  // int n, m, k;
  // cin >> n >> m >> k;

  vector<vector<pair<int,ll>>> g(n);
  // int x, y, l;
  int x, y;
  for (int i{0}; i < m; ++i) {
    // cin >> x >> y >> l;
    x = r[i][0];
    y = r[i][1];
    g[x].push_back({y, l[i]});
    g[y].push_back({x, l[i]});
  }

  vector<int> exit(k);
  vector<ll> dist(n, LLONG_MAX);
  for (int i{0}; i < k; ++i) {
    // cin >> exit[i];
    exit[i] = p[i];
    dist[exit[i]] = 0;
    pq.push({0, exit[i]});
  }

  while (pq.size()) {
    ll d = pq.top().first;
    int u = pq.top().second;
    pq.pop();
    if (d != dist[u]) continue;
    for (auto &v: g[u]) {
      if (d + v.second < dist[v.first]) {
        dist[v.first] = d + v.second;
        pq.push({dist[v.first], v.first});
      }
    }
  }

  vector<bool> visited(n);
  queue<int> q;
  for (int i{0}; i < k; ++i) {
    q.push(exit[i]);
  }
  vector<pair<ll,int>> dists(n);
  for (int i{0}; i < n; ++i) {
    dists[i] = {dist[i], i};
  }
  sort(dists.begin(), dists.end());

  // for (int i{0}; i < n; ++i) {
  //   cout << dist[i] << '\n';
  // }

  vector<ll> ans(n);
  for (auto &disti: dists) {
    int i = disti.second;
    ll mn{LLONG_MAX};
    int mni{-1};
    for (auto &v: g[i]) {
      // cout << (dist[v.first] < dist[i]) << ' ' << i << ' ' << v.first << ' ' << ans[v.first] << ' ' << v.second << "\n";
      if (dist[v.first] < dist[i] && ans[v.first]+v.second < mn) {
        mn = ans[v.first]+v.second;
        mni = v.first;
      }
    }
    mn = LLONG_MAX;
    for (auto &v: g[i]) {
      if (dist[v.first] < dist[i] && v.first != mni && ans[v.first]+v.second < mn) {
        mn = ans[v.first]+v.second;
      }
    }
    ans[i] = mn == LLONG_MAX ? 0 : mn;
  }

  return ans[0];

  return 0;
}

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