Submission #892876

#	Time	Username	Problem	Language	Result	Execution time	Memory
892876		eysbutno	악어의 지하 도시 (IOI11_crocodile)	C++17	0 / 100	1 ms	4444 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define pb push_back
#define ins insert
#define f first 
#define s second 

int travel_plan(int N, int M, int R[][2], 
    int L[], int k, int p[]) {
    const ll INF = 1e18;
    int n = N, m = M;
    vector<vector<pii>> adj(n);
    for (int i = 0; i < m; i++) {
        int x = R[i][0], y = R[i][1],
            w = L[i];
        adj[x].pb({y, w});
        adj[y].pb({x, w});
    }
    vector<ll> dist(n, INF), fin(n, INF);
    priority_queue<pll> pq;
    for (int i = 0; i < k; i++) {
        pq.push({0, p[i]});
        dist[p[i]] = 0;
    }
    while (!pq.empty()) {
        auto N = pq.top(); pq.pop();
        ll t = -N.f, u = N.s;
        if (dist[u] != t) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({-dist[v], v});
            }
        }
    }
    fin[0] = 0;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto N = pq.top(); pq.pop();
        ll t = -N.f, u = N.s;
        if (fin[u] != t) continue;
        vector<vector<ll>> pos;
        for (auto [v, w] : adj[u]) {
            pos.pb({w + dist[v], v, w});
        }
        sort(all(pos), [&](auto& x, auto& y) {
            return x[0] < y[0];
        });
        for (int i = 1; i < sz(pos); i++) {
            ll v = pos[i][1], w = pos[i][2];
            if (t + w < fin[v]) {
                fin[v] = t + w;
                pq.push({-fin[v], v});
            }
        }
    }
    ll res = 2e9;
    for (int i = 0; i < k; i++) {
        smin(res, fin[p[i]]);
    }
    return (int) res;
}

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