Submission #723470

#	Time	Username	Problem	Language	Result	Execution time	Memory
723470		yashsingh	Crocodile's Underground City (IOI11_crocodile)	C++17	Compilation error	0 ms	0 KiB

crocodile

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
  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;
  for (int i{0}; i < m; ++i) {
    cin >> x >> y >> l;
    g[x].push_back({y, l});
    g[y].push_back({x, l});
  }

  vector<int> exit(k);
  vector<ll> dist(n, LLONG_MAX);
  for (int i{0}; i < k; ++i) {
    cin >> exit[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;
  }

  cout << ans[0] << '\n';

  return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccd1dLwP.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccBBXvAO.o:crocodile.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccd1dLwP.o: in function `main':
grader.cpp:(.text.startup+0x36): undefined reference to `travel_plan(int, int, int (*) [2], int*, int, int*)'
collect2: error: ld returned 1 exit status