oj.uz

답안 #421035

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
421035 2021-06-08T16:46:25 Z Alex_tz307 악어의 지하 도시 (IOI11_crocodile) C++17
0 / 100
 2 ms 2636 KB 
#include <bits/stdc++.h>
#include "crocodile.h"

using namespace std;
using int64 = long long;

const int MAXN = 1e5;
const int64 INF = 1e18L;
bitset<MAXN> is_exit;
vector<pair<int,int>> G[MAXN];
int64 d1[MAXN], d2[MAXN];

int Dijkstra(int n) {
  priority_queue<pair<int64,int>, vector<pair<int64,int>>, greater<pair<int64,int>>> pq;
  for (int u = 0; u < n; ++u)
    if (is_exit[u])
      pq.emplace(0, u);
    else d1[u] = d2[u] = INF;
  while (!pq.empty()) {
    int64 d;
    int u;
    tie(d, u) = pq.top();
    pq.pop();
    for (auto it : G[u]) {
      int v, w;
      tie(v, w) = it;
      int64 cost = d2[u] + w;
      bool is_improved = false;
      if (d1[v] >= cost) {
        d2[v] = d1[v];
        d1[v] = cost;
        is_improved = true;
      } else {
        if (d2[v] > cost) {
          d2[v] = cost;
          is_improved = true;
        }
      }
      if (is_improved)
        pq.emplace(d2[v], v);
    }
  }
  return d2[0];
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  for (int i = 0; i < M; ++i) {
    int u = R[i][0], v = R[i][1], w = L[i];
    G[u].emplace_back(v, w);
    G[v].emplace_back(u, w);
  }
  for (int i = 0; i < K; ++i)
    is_exit[P[i]] = true;
  return Dijkstra(N);
}

/* int n, m, R[MAXN][2], L[MAXN], k, P[MAXN], sol;

void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
}

int main() {
  fastIO();
  cin >> n >> m >> k;
  for (int i = 0; i < m; ++i)
    cin >> R[i][0] >> R[i][1] >> L[i];
  for (int i = 0; i < k; ++i)
    cin >> P[i];
  cin >> sol;
  int ans = travel_plan(n, m, R, L, k, P);
  if (ans == sol)
    cout << "OK\n";
  else {
    cout << "WA\n";
    cout << "USER OUTPUT: " << ans << '\n';
    cout << "EXPECTED ANSWER: " << sol << '\n';
  }
  return 0;
} */

Subtask #1
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -