제출 #1162951

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162951		HappyCapybara	악어의 지하 도시 (IOI11_crocodile)	C++17	100 / 100	267 ms	47760 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

ll x = pow(10, 10);

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
  vector<vector<pair<int,int>>> g(N);
  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]});
  }
  vector<pair<ll,ll>> d(N, {x, x});
  priority_queue<pair<ll,int>> pq;
  for (int i=0; i<K; i++){
    d[P[i]] = {0, 0};
    pq.push({-d[P[i]].second, P[i]});
  }
  vector<bool> seen(N, false);
  while (!pq.empty()){
    int cur = pq.top().second;
    ll dist = -pq.top().first;
    pq.pop();
    if (seen[cur]) continue;
    seen[cur] = true; 
    for (auto [next, l] : g[cur]){
      if (d[next].second > dist+l){
        d[next].second = dist+l;
        if (d[next].first > d[next].second) swap(d[next].first, d[next].second);
        if (d[next].second != x) pq.push({-d[next].second, next});
      }
    }
  }
  return d[0].second;
}

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