제출 #1163843

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163843		sasde	Relay Marathon (NOI20_relaymarathon)	C++20	17 / 100	6086 ms	332832 KiB

RelayMarathon

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const ll INF = 1e18;
 
struct Edge {
    int to, w;
};
 
struct State {
    ll d;
    int u, src;
    bool operator>(const State &o) const {
        return d > o.d;
    }
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M, K;
    cin >> N >> M >> K;
    
    vector<vector<Edge>> graph(N+1);
    for (int i = 0; i < M; i++){
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
    
    vector<int> special(K);
    vector<bool> isSpecial(N+1, false);
    for (int i = 0; i < K; i++){
        cin >> special[i];
        isSpecial[special[i]] = true;
    }
    
    vector<vector<pair<ll,int>>> best(N+1); 
    priority_queue<State, vector<State>, greater<State>> pq;
    
    for (int s : special) {
        best[s].push_back({0, s});
        pq.push({0, s, s});
    }
    
    while(!pq.empty()){
        State st = pq.top();
        pq.pop();
        if(st.d != best[st.u][0].first && best[st.u].size() && st.d > best[st.u][0].first)
            continue;
        int u = st.u;
        for(auto &edge : graph[u]){
            int v = edge.to;
            ll nd = st.d + edge.w;
            bool canPush = false;
            bool already = false;
            for(auto &p : best[v]){
                if(p.second == st.src){
                    if(nd < p.first){
                        p.first = nd;
                        canPush = true;
                    }
                    already = true;
                    break;
                }
            }
            if(!already){
                best[v].push_back({nd, st.src});
                canPush = true;
            }
            if(best[v].size() > 2){
                sort(best[v].begin(), best[v].end());
                best[v].resize(2);
            }
            if(canPush)
                pq.push({nd, v, st.src});
        }
    }
    
    map<pair<int,int>, ll> cand;
    
    for (int u = 1; u <= N; u++){
        if(best[u].size() >= 2){
            sort(best[u].begin(), best[u].end());
            ll cost = best[u][0].first + best[u][1].first;
            int a = best[u][0].second, b = best[u][1].second;
            if(a > b) swap(a, b);
            if(cand.find({a,b}) == cand.end() || cost < cand[{a,b}])
                cand[{a,b}] = cost;
        }
    }
    
    for (int u = 1; u <= N; u++){
        for(auto &edge : graph[u]){
            int v = edge.to;
            // Với mỗi cặp (u,v), xem xét tất cả các khả năng đến từ u và v.
            for(auto &p1 : best[u]){
                for(auto &p2 : best[v]){
                    if(p1.second == p2.second) continue;
                    ll cost = p1.first + edge.w + p2.first;
                    int a = p1.second, b = p2.second;
                    if(a > b) swap(a, b);
                    if(cand.find({a,b}) == cand.end() || cost < cand[{a,b}])
                        cand[{a,b}] = cost;
                }
            }
        }
    }
    
    vector<tuple<ll,int,int>> pairs;
    for(auto &entry : cand){
        pairs.push_back({entry.second, entry.first.first, entry.first.second});
    }
    sort(pairs.begin(), pairs.end());
    
    ll ans = INF;
    int sz = pairs.size();
    int L = min(sz, 5000); 
    for (int i = 0; i < L; i++){
        ll cost1;
        int a, b;
        tie(cost1, a, b) = pairs[i];
        for (int j = i+1; j < L; j++){
            ll cost2;
            int c, d;
            tie(cost2, c, d) = pairs[j];
            // Kiểm tra 2 cặp có giao nhau không
            if(a == c || a == d || b == c || b == d)
                continue;
            ans = min(ans, cost1 + cost2);
            break;
        }
    }
    
    cout << ans << "\n";
    return 0;
}

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