답안 #786880

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
786880 2023-07-18T14:11:25 Z jakobrs 악어의 지하 도시 (IOI11_crocodile) C++17
0 / 100
1 ms 212 KB
#include "crocodile.h"

#include <tuple>
#include <utility>
#include <iostream>
#include <queue>
#include <vector>

using i64 = int64_t;

struct Node {
  i64 dist;
  i64 index;

  bool operator<(const Node &rhs) const {
    return std::tie(rhs.dist, index) < std::tie(dist, rhs.index);
  }
};

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  std::vector<std::vector<std::pair<i64, i64>>> adj(N);
  for (i64 i = 0; i < M; i++) {
    adj[R[i][0]].push_back({R[i][1], L[i]});
    adj[R[i][1]].push_back({R[i][0], L[i]});
  }

  std::vector<i64> distances(N, 1e18);
  std::vector<i64> distances2(N, 1e18);
  std::priority_queue<Node> pq;
  for (i64 i = 0; i < K; i++) {
    distances[P[i]] = 0;
    distances2[P[i]] = 0;
    pq.push(Node{.dist = 0, .index = P[i]});
  }
  while (!pq.empty()) {
    auto [dist, index] = pq.top();
    pq.pop();

    if (dist > distances2[index])
      continue;
    if (index == 0)
      return dist;

    for (auto [x, d] : adj[index]) {
      i64 new_dist = dist + d;
      if (new_dist < distances[x]) {
        if (distances[x] < distances2[x]) {
          pq.push(Node{.dist = distances2[x], .index = x});
        }
        distances2[x] = distances[x];
        distances[x] = new_dist;
      } else if (new_dist < distances2[x]) {
        distances2[x] = new_dist;

        pq.push(Node{.dist = new_dist, .index = x});
      }
    }
  }
  return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -