제출 #1358447

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

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define pii pair<int, int>

using namespace std;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    vector<pii> adj[N];
    int dis[2][N];
    for (int i = 0; i < N; i++) dis[0][i] = dis[1][i] = INT_MAX;
    for (int i = 0; i < M; i++) {
        int u = R[i][0], v = R[i][1];
        adj[u].emplace_back(L[i], v);
        adj[v].emplace_back(L[i], u);
    }
    priority_queue<pii, vector<pii>, greater<pii>> q;
    for (int i = 0; i < K; i++) dis[0][P[i]] = dis[1][P[i]] = 0, q.emplace(0, P[i]);
    while (!q.empty()) {
        auto [w, u] = q.top();
        q.pop();
        if (w > dis[1][u]) continue;
        for (auto &[ww, v] : adj[u]) {
            if (ww + w < dis[0][v]) dis[1][v] = dis[0][v], dis[0][v] = ww + w, q.emplace(dis[1][v], v);
            else if (ww + w < dis[1][v]) dis[1][v] = ww + w, q.emplace(ww + w, v);
        }
    }
    return dis[1][0];
}

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