제출 #1330857

#제출 시각아이디문제언어결과실행 시간메모리
1330857Double_SlashRelay Marathon (NOI20_relaymarathon)C++20
100 / 100
3340 ms150256 KiB
#pragma GCC optimize("O3,unroll-loops,inline")
#include <bits/stdc++.h>
#pragma GCC target("avx2")
 
using namespace std;
#define all(x) x.begin(), x.end()
using pint = pair<int, int>;
 
const int INF = 1e9;
 
int n, m, k;
vector<pint> adj[100001];
bool s[100001];
 
array<int, 3> mpair() {
    vector<int> seen(n + 1), dist(n + 1, INF);
    priority_queue<array<int, 3>> pq;
    for (int i = 1; i <= n; ++i) {
        if (s[i]) pq.push({0, i, i});
    }
    array<int, 3> mn{INF};
    while (not pq.empty()) {
        auto [d, i, p] = pq.top();
        pq.pop();
        if (not seen[i]) {
            seen[i] = p;
            dist[i] = -d;
        } else {
            if (seen[i] != p) mn = min(mn, array<int, 3>{-d + dist[i], seen[i], p});
            continue;
        }
        if (-d >= mn[0]) continue;
        for (auto &[j, x]: adj[i]) pq.push({d - x, j, seen[i]});
    }
    return mn;
}

vector<pint> sssp(int S) {
    vector<int> dist(n + 1, INF);
    priority_queue<pint> pq;
    pq.emplace(0, S);
    vector<pint> ret;
    while (not pq.empty()) {
        auto [d, i] = pq.top();
        pq.pop();
        if (-d >= dist[i]) continue;
        if (s[i]) {
            ret.emplace_back(i, -d);
            if (ret.size() == 2) return ret;
        }
        dist[i] = -d;
        for (auto &[j, x]: adj[i]) pq.emplace(d - x, j);
    }
    return {};
}
 
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cin >> n >> m >> k;
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    while (k--) {
        int i;
        cin >> i;
        s[i] = true;
    }
    auto [d, a, b] = mpair();
    s[a] = s[b] = false;
    int ans = d + mpair()[0];
    auto dista = sssp(a), distb = sssp(b);
    if (dista.size() == 2 and distb.size() == 2) {
        if (dista[0].first != distb[0].first) ans = min(ans, dista[0].second + distb[0].second);
        else ans = min({ans, dista[0].second + distb[1].second, dista[1].second + distb[0].second});
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...