제출 #1170274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170274		susanthenerd	Relay Marathon (NOI20_relaymarathon)	C++20	30 / 100	938 ms	137020 KiB

RelayMarathon

#include <iostream>
#include <vector>
#include <tuple>
#include <queue>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<pair<int, ll> > > adj(n + 1);

    while (m--) {
        int u, v;
        ll c;
        cin >> u >> v >> c;
        adj[u].emplace_back(v, c);
        adj[v].emplace_back(u, c);
    }


    vector<bool> special(n + 1);
    for (ll i = 0; i < k; ++i) {
        int x;
        cin >> x;
        special[x] = true;
    }


    auto dijkstra_all = [&] {
        priority_queue<pair<ll, int> > pq;
        vector<ll> dist(n + 1, 1e18);
        vector<int> per(n + 1);
        for (int i = 1; i <= n; ++i) {
            if (special[i]) {
                pq.emplace(0, i);
                per[i] = i;
                dist[i] = 0;
            }
        }

        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();

            if (-d != dist[u])
                continue;
            for (auto &[v, c]: adj[u]) {
                if (dist[u] + c < dist[v]) {
                    per[v] = per[u];
                    dist[v] = dist[u] + c;
                    pq.emplace(-dist[v], v);
                }
            }
        }

        ll ans = 1e18;
        int a = 0, b = 0;
        for (int u = 1; u <= n; ++u) {
            for (auto &[v, c]: adj[u]) {
                if (per[u] != per[v] && dist[u] + dist[v] + c < ans) {
                    ans = dist[u] + dist[v] + c;
                    a = per[u];
                    b = per[v];
                }
            }
        }

        return tuple{ans, a, b};
    };

    auto dijkstra = [&](int x)-> pair<ll, int> {
        priority_queue<pair<ll, int> > pq;
        vector<ll> dist(n + 1, 1e18);
        dist[x] = 0;
        pq.emplace(0, x);

        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (special[u]) return {-d, u};
            if (dist[u] != d) continue;
            for (auto &[v, c]: adj[u]) {
                if (dist[u] + c < dist[v]) {
                    dist[v] = dist[u] + c;
                    pq.emplace(-dist[v], v);
                }
            }
        }

        return {1e18, 0};
    };

    ll ans = 1e18;

    auto [cost1, x, y] = dijkstra_all();
    special[x] = special[y] = false;
    ans = min(ans, cost1 + get<0>(dijkstra_all()));


    auto [cost2, a] = dijkstra(x);
    special[a] = false;
    ans = min(ans, cost2 + dijkstra(y).first);
    special[a] = true;


    auto [cost3, b] = dijkstra(y);
    special[b] = false;
    ans = min(ans, cost3 + dijkstra(x).first);

    cout << ans << '\n';
}

/*
5 4 4
1 2 1
3 4 2
4 5 5
5 3 8
3 1 5 2
*/

/*
6 6 4
1 2 5
2 4 7
4 6 50
6 5 3
1 5 15
3 5 6
1 5 4 6
*/

• Subtask 1: 5 / 5
• Subtask 2: 0 / 12
• Subtask 3: 25 / 25
• Subtask 4: 0 / 58