제출 #384947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
384947		izhang05	Crocodile's Underground City (IOI11_crocodile)	C++17	46 / 100	5 ms	1132 KiB

crocodile

#include "crocodile.h"
#ifdef LOCAL
#include "crocodile_grader.cpp"
#endif

#include <bits/stdc++.h>

using namespace std;
#define int long long
//#define DEBUG
const int maxn = 1e3 + 5, inf = 1e18;
int sol[maxn];
vector<pair<int, int>> adj[maxn];
pair<int, int> c[maxn];

set<pair<int, int>> q;

void comb(int node, int cost) {
    if (cost < c[node].first) {
        if (c[node].second != inf) {
            q.erase({c[node].second, node});
        }
        swap(c[node].first, c[node].second);
        c[node].first = cost;
        if (c[node].second != inf) {
            q.insert({c[node].second, node});
        }

    } else if (cost < c[node].second) {
        if (c[node].second != inf) {
            q.erase({c[node].second, node});
        }
        c[node].second = cost;
        q.insert({c[node].second, node});
    }
}

signed travel_plan(signed n, signed m, signed r[][2], signed l[], signed k, signed p[]) {
    for (int i = 0; i < m; ++i) {
        int a = r[i][0], b = r[i][1], cost = l[i];
        adj[a].emplace_back(b, cost);
        adj[b].emplace_back(a, cost);
    }
    for (int i = 0; i < n; ++i) {
        sol[i] = inf;
        c[i] = {inf, inf};
    }
    for (int i = 0; i < k; ++i) {
        sol[p[i]] = 0;
        for (auto j : adj[p[i]]) {
            comb(j.first, j.second);
        }
    }
    while (sol[0] == inf) {
        pair<int, int> cur = *q.begin();
        int node = cur.second, cost = cur.first;
        sol[node] = cur.first;
        q.erase(q.begin());
        for (auto i : adj[node]) {
            if (sol[i.first] == inf) {
                comb(i.first, cost + i.second);
            }
        }
    }
#ifdef DEBUG
    for (int j = 0; j < n; ++j) {
        cout << sol[j] << "\n";
    }
#endif
    return sol[0];
}

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