제출 #1193746

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

crocodile

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

using pii = pair<int, int>;

#define X first
#define Y second

const int MXN = 1e5+5;
const int inf = 1e9;

vector<pii> g[MXN];
int dis[MXN];
bool mark[MXN];
pii st[MXN];
priority_queue<pii> pq;

inline void upd(int v, int d) {
  dis[v] = d;
  for(auto [u, w] : g[v])
    if(d+w<st[u].Y) {
      st[u].Y = d+w;
      if(st[u].Y<st[u].X) swap(st[u].X, st[u].Y);
      pq.push({-st[u].Y, u});
    }
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  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]});
  }
  fill(st, st+N, pii(inf, inf));
  for(int i=0; i<N; i++) upd(i, inf);
  for(int i=0; i<K; i++) upd(P[i], 0), mark[P[i]] = 1;
  while(!pq.empty()) {
    int d = -pq.top().X;
    int v = pq.top().Y;
    pq.pop();
    if(mark[v]) continue;
    upd(v, d);
    mark[v] = 1;
  }
  return dis[0];
}

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