제출 #1209187

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1209187		pera	악어의 지하 도시 (IOI11_crocodile)	C++20	89 / 100	327 ms	73680 KiB

crocodile

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

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
   vector<vector<pair<int , long long>>> g(N);
   for(int i = 0;i < M;i ++){
      g[R[i][0]].emplace_back(R[i][1] , L[i]);
      g[R[i][1]].emplace_back(R[i][0] , L[i]);
   }
   vector<vector<long long>> dist(N , vector<long long>(2 , -1));
   priority_queue<pair<long long , int> , vector<pair<long long , int>> , greater<pair<long long , int>>> pq;
   for(int i = 0;i < K;i ++){
      for(int w = 0;w < 2;w ++){
         dist[P[i]][w] = 0;
      }
      pq.push(pair<long long , int>{0LL , P[i]});
   }
   while((int)pq.size()){
      auto [d , u] = pq.top();
      pq.pop();
      if(dist[u][1] != d){
         continue;
      }
      for(auto [v , w] : g[u]){
         d += w;
         if(dist[v][0] == -1){
            dist[v][0] = d;
         }else if(dist[v][1] == -1){
            dist[v][1] = d;
            if(dist[v][1] < dist[v][0]){
               swap(dist[v][1] , dist[v][0]);
            }
            pq.push(pair<int , long long>{dist[v][1] , v});
         }else{
            if(d < dist[v][0]){
               swap(dist[v][0] , dist[v][1]);
               dist[v][0] = d;
               pq.push(pair<int , long long>{dist[v][1] , v});
            }else if(d < dist[v][1]){
               dist[v][1] = d;
               pq.push(pair<int , long long>{d , v});
            }
         }
         d -= w;
      }
   }
   return dist[0][1];
}

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