제출 #1358523

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1358523		hyyh	악어의 지하 도시 (IOI11_crocodile)	C++20	100 / 100	364 ms	55160 KiB

crocodile

#include "crocodile.h"
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

using pii = pair<int,int>;
using ll = long long;

#define endl '\n'

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]){
  priority_queue<pii,vector<pii>,greater<pii>> pq;
  vector<vector<pii>> adj(n);
  vector<int> cnt(n);
  vector<int> walk(n);
  for(int i{};i < k;i++){
    pq.emplace(0,P[i]);
    cnt[P[i]]++;
  }
  for(int i{};i < m;i++){
    int st = R[i][0];
    int ed = R[i][1];
    adj[st].emplace_back(L[i],ed);
    adj[ed].emplace_back(L[i],st);
  }
  while(!pq.empty()){
    auto [cost,pos] = pq.top();pq.pop();
    if(++cnt[pos] != 2) continue;
    //cout << cost << " " << pos << endl;
    walk[pos] = cost;
    for(auto [w,k]:adj[pos]){
      if(cnt[k] > 2) continue;
      pq.emplace(w+cost,k);
    }
  }
  return walk[0];
}

• 서브태스크 1: 46 / 46
• 서브태스크 2: 43 / 43
• 서브태스크 3: 11 / 11