제출 #1315416

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

crocodile

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

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]});
  }
  multiset<pair<int, int>> m;
  vector<int> vis(N);
  vector<int> dis(N, 1e9);
  for(int i = 0; i < K; i++){
    m.insert({0, P[i]});
    vis[P[i]] = 1;
  }
  while(m.size() > 0){
    auto [time, k] = *m.begin();
    m.erase(m.begin());
    vis[k]++;
    if(vis[k] != 2) continue;
    dis[k] = time;
    for(int i = 0; i < g[k].size(); i++){
      if(vis[g[k][i].first] >= 2) continue;
      m.insert({time+g[k][i].second, g[k][i].first});
    }
  }
  return dis[0];
}

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