제출 #335450

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
335450		codebuster_10	악어의 지하 도시 (IOI11_crocodile)	C++17	0 / 100	1 ms	384 KiB

crocodile

#include <bits/stdc++.h>
using namespace std ;
#define f(i,a,b) for(int i=a;i<b;++i)

const int64_t INF = 1e12 ; 
int travel_plan(int N, int M, int R[][2],int L[], int K,int P[]){
  vector< vector< array<int,2> > > g(N) ;
  f(i,0,M){
    int u = R[i][0], v = R[i][1], w = L[i] ;
    g[u].push_back({v, w}) ;
    g[v].push_back({u, w}) ;
  }
  vector< array<int64_t,2> > best(N, {INF, INF}) ;
  f(i,0,K) best[P[i]][0] = best[P[i]][1] = 0 ;
  priority_queue< pair<int64_t,int> > p ;
  f(i,0,N){
    p.push({-best[i][1],i}) ;
  }
  while(int(p.size())){
    int i = p.top().second ;
    p.pop() ;
    for(auto [j,w]:g[i]){
      int NewDis = w + best[i][1] ;
      if(NewDis < best[j][0]){
        best[j][1] = best[j][0] ;
        best[j][0] = NewDis ;
        p.push({-best[j][1],j}) ;
      }else if(NewDis < best[j][1]){
        best[j][1] = NewDis ;
        p.push({-best[j][1],j}) ;
      }
    }
  }
  return int(best[0][1]) ;
}

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