Submission #1170260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170260		susanthenerd	Relay Marathon (NOI20_relaymarathon)	C++20	0 / 100	22 ms	7592 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 = [&] {
        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], c);
                }
            }
        }


        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 = u;
                    b = v;
                }
            }
        }

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

    auto [cost1, x, y] = dijkstra();
    special[x] = false;
    special[y] = false;

    auto [cost2, a, b] = dijkstra();
    cout << cost1 + cost2 << '\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: 0 / 5
• Subtask 2: 0 / 12
• Subtask 3: 0 / 25
• Subtask 4: 0 / 58