제출 #1295118

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

crocodile

#include "crocodile.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>

#define MAX_N 100005
#define MAX_M 1000005
#define ll long long
#define fi first
#define se second
using namespace std;
ll inf = 1000000000;

vector<pair<int,ll>>a[MAX_M];
int n,m,k,x,y,w;
int travel_plan(int N,int M,int R[][2],int L[],int K,int P[]){
  n=N,m=M,k=K;
  for (int i=0;i<m;i++){
    x=R[i][0],y=R[i][1],w=L[i];
    a[x].push_back({y,w});
    a[y].push_back({x,w});
  }
  vector<ll>di(n,inf);
  vector<int>vi1(n);
  vector<int>vi(n);
  priority_queue<pair<int,int>>o;
  for (int i=0;i<k;i++){
    o.push({0,P[i]});
    vi1[P[i]]=1;
    di[P[i]]=0;
  }
  while (o.size()){
    auto hi=o.top();
    o.pop();
    int h=hi.se;
    if (!vi1[h]){
      vi1[h]=1;
      continue;
    }
    if (vi[h])continue;
    vi[h]=1;
    di[h]=-hi.fi;
    for (auto [i,w]:a[h]){
      if (vi[i])continue;
      o.push({-1*(di[h]+w),i});
    }
  }
  return di[0];
}

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