Submission #998501

#	Time	Username	Problem	Language	Result	Execution time	Memory
998501		Alfraganus	악어의 지하 도시 (IOI11_crocodile)	C++17	100 / 100	471 ms	60496 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<array<int, 2>>> graph(n);
  for(int i = 0; i < m; i ++)
    graph[r[i][0]].push_back({r[i][1], l[i]}), graph[r[i][1]].push_back({r[i][0], l[i]});
  vector<int> mins1(n, 1e9), mins2(n, 1e9);
  for(int i = 0; i < k; i ++)
    mins1[p[i]] = 0, mins2[p[i]] = 0;
  set<array<int, 2>> st;
  for(int i = 0; i < k; i ++)
    st.insert({0, p[i]});
  while(!st.empty()){
    auto [d, x] = *st.begin();
    st.erase(st.begin());

    for(auto [y, t] : graph[x]){
      if(mins1[y] > t + d){
        st.erase({mins2[y], y});
        mins2[y] = mins1[y];
        mins1[y] = t + d;
        st.insert({mins2[y], y});
      }
      else if(mins2[y] > t + d){
        st.erase({mins2[y], y});
        mins2[y] = t + d;
        st.insert({mins2[y], y});
      }
    }
  }
  return mins2[0];
}

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