제출 #1368049

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368049		eyadooz	악어의 지하 도시 (IOI11_crocodile)	C++20	89 / 100	262 ms	76964 KiB

crocodile

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define endl '\n'

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    vector<pll> adj[N+1];
    ll dis[N+1]={}, dis2[N+1]={};
    for(int i=0;i<=N;i++) dis[i]=dis2[i]=INT_MAX;
    for(int i = 0;i < M;i++) 
    {
        int u=R[i][0], v=R[i][1];
        adj[u].pb({v, L[i]});
        adj[v].pb({u, L[i]});
    }
    priority_queue<pll> pq;
    for(int i = 0;i < K;i++) {
        auto u=P[i];
        dis[u]=dis2[u]=0;
        pq.push({0,u});
    }
    while(sz(pq)) {
        auto[cw, x]=pq.top();
        pq.pop();
        cw*=-1;
        if(cw!=dis2[x]) continue;
        for(auto[i, w] : adj[x]) {
            if(cw+w<dis[i]) {
                dis2[i]=dis[i];
                dis[i]=cw+w;
                pq.push({-dis2[i], i});
            }
            else if(cw+w<dis2[i]) {
                dis2[i]=cw+w;
                pq.push({-dis2[i], i});
            }
        }
    }
    return dis2[0];
}   

• 서브태스크 1: 46 / 46
• 서브태스크 2: 43 / 43
• 서브태스크 3: 0 / 11