제출 #1092595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1092595		PagodePaiva	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	310 ms	61660 KiB

crocodile

#include<bits/stdc++.h>
#include "crocodile.h"
#define inf 1e9 + 10

using namespace std;

const int N = 100010;
vector <pair <int, int>> g[N];
int dist1[N], dist2[N], pai[N];

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]){
  for(int i = 0;i < m;i++){
    int a = R[i][0], b = R[i][1], w = L[i];
    g[a].push_back({b, w});
    g[b].push_back({a, w});
  }
  for(int i = 0;i <= n;i++) dist1[i] = dist2[i] = inf;
  priority_queue <pair <int, int>> pq;
  for(int i = 0;i < k;i++){
    dist1[P[i]] = dist2[P[i]] = 0;
    pq.push({0, P[i]});
  }
  while(!pq.empty()){
    auto [d, v] = pq.top();
    pq.pop();
    d *= -1;
    if(d != dist2[v]) continue;
    for(auto [x, w] : g[v]){
      if(dist1[x] > dist2[v] + w){
        if(pai[x] != v) {
          dist2[x] = dist1[x];
          if(dist2[x] != inf) pq.push({-dist2[x], x});
        }
        dist1[x] = dist2[v] + w;
        pai[x] = v;
      }
      else if(dist2[x] > dist2[v] + w and pai[x] != v){
        dist2[x] = dist2[v] + w;
        pq.push({-dist2[x], x});
      }
    }
  }
  return dist2[0];
}

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