oj.uz

Submission #723473

# Submission time Handle Problem Language Result Execution time Memory
723473 2023-04-13T22:40:39 Z yashsingh Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 1 ms 340 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -