제출 #999541

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
999541		Mr_Husanboy	악어의 지하 도시 (IOI11_crocodile)	C++17	100 / 100	308 ms	48664 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;
#define ll int

template<typename T>
int len(T &a){return a.size();}
const int inf = 1e9 + 1;
const ll infl = 1e9;
#define ss second
#define ff first
#define all(a) (a).begin(), (a).end()


int travel_plan(int n, int m, int r[][2], int L[], int K, int P[])
{
  vector<vector<pair<int,int>>> g(n);
  //cout << "done" << endl;
  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]});
  }
  
  vector<pair<ll, ll>> dis(n, {infl, infl});
  priority_queue<pair<ll, int>> q;
  for(int i = 0; i < K; i ++){
    q.push({0, P[i]});
    dis[P[i]] = {0, 0};
  }
  vector<int> vis(n);

  while(!q.empty()){
    int t = q.top().ss;
    q.pop();
    if(vis[t]) continue;
    vis[t] = 1;
    for(auto [u, w] : g[t]){
      if(dis[u].ff > dis[t].ss + w){
        dis[u].ss = dis[u].ff;
        q.push({-dis[u].ss, u});
        dis[u].ff = dis[t].ss + w;
      }else if(dis[u].ss > dis[t].ss + w){
        dis[u].ss = dis[t].ss + w;
        q.push({-dis[u].ss, u});
      }
    }
  }
  return dis[0].ss;
}

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