제출 #363220

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
363220		Pety	악어의 지하 도시 (IOI11_crocodile)	C++14	100 / 100	853 ms	67444 KiB

crocodile

#include <bits/stdc++.h>
#define pii pair<int, int>

using namespace std;

vector<pii>G[100002];
int viz[100002];
int dist[100002], dist2[100002];

int travel_plan (int n, int m, int r[][2], int l[], int k, int p[]) {
  for (int i = 0; i < k; i++) {
    if (!p[i])
      return 0;
  }
  for (int i = 0; i < m; i++) {
    G[r[i][0]].push_back({r[i][1], l[i]});
    G[r[i][1]].push_back({r[i][0], l[i]});
  }
  queue<int>q;
  priority_queue<pii, vector<pii>, greater<pii> >pq;
  for (int i = 0; i < n; i++)
    dist[i] = 1e9;
  for (int i = 0; i < k; i++) {
    dist[p[i]] = 0;
    viz[p[i]] = 1;
    pq.push({0, p[i]});
  }
  while (pq.size()) {
    int nod =  pq.top().second;
    int aux = pq.top().first;
    pq.pop();
    if (viz[nod] == 2)
      continue;
    if (viz[nod] == 0) {
      viz[nod] = 1;
      continue;
    }
    if (viz[nod] == 1)
      viz[nod] = 2;
    dist[nod] = aux;
    for (auto it : G[nod]) {
      if (viz[it.first] < 2)
        pq.push({dist[nod] + it.second, it.first});

    }
  }
  return dist[0];
}

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