제출 #709651

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

crocodile

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 7;

vector <pair <int, int>> adj[N];
bool special[N];
int n, m, k;

namespace sub2 {
    long long d[N][2];
    struct state {
        long long dist;
        int u, t;

        bool operator < (const state &other) const {
            return dist > other.dist;
        }
    };

    long long solve() {
        priority_queue <state> heap;

        memset(d, 0x3f, sizeof d);

        for (int i = 0; i < n; ++i) {
            if (special[i] == false) continue;
            d[i][0] = d[i][1] = 0;
            heap.push({0, i, 0});
        }

        while (heap.size()) {
            auto [dist, u, t] = heap.top();
            heap.pop();

            if (dist != d[u][t]) continue;

            for (auto [v, w] : adj[u]) {
                if (d[v][0] > dist + w) {
                    if (d[v][0] < (long long) 1e18 && d[v][1] != d[v][0]) {
                        d[v][1] = d[v][0];
                        heap.push({d[v][1], v, 1});
                    }
                    d[v][0] = dist + w;
                } else if (d[v][1] > dist + w) {
                    d[v][1] = dist + w;
                    heap.push({dist + w, v, 1});
                }
            }
        }
        return d[0][1];
    }
}

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) {
        int u = R[i][0], v = R[i][1], w = L[i];
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    for (int i = 0; i < k; ++i) {
        special[P[i]] = true;
    }
    return sub2::solve();
}

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