Submission #1306265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306265		efsdfwe	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	177 ms	19284 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = 4e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    int s, t;
    cin >> s >> t;
    int u, v;
    cin >> u >> v;
    s--; t--; u--; v--;  // 0-indexed
    
    vector<vector<tuple<int,int,ll>>> g(n);
    for (int i = 0; i < m; i++) {
        int a, b; ll c;
        cin >> a >> b >> c;
        a--; b--;
        g[a].emplace_back(b, i, c);
        g[b].emplace_back(a, i, c);
    }
    
    auto dijkstra = [&](int start) -> vector<ll> {
        vector<ll> dist(n, INF);
        dist[start] = 0;
        priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
        pq.emplace(0, start);
        while (!pq.empty()) {
            auto [d, x] = pq.top(); pq.pop();
            if (d > dist[x]) continue;
            for (auto [y, _, c] : g[x]) {
                if (dist[y] > dist[x] + c) {
                    dist[y] = dist[x] + c;
                    pq.emplace(dist[y], y);
                }
            }
        }
        return dist;
    };
    
    auto ds = dijkstra(s);
    auto dt = dijkstra(t);
    auto du = dijkstra(u);
    auto dv = dijkstra(v);
    
    ll dist_st = ds[t];
    ll ans = du[v];
    
    // Перебор всех рёбер как кандидатов на покрытие
    for (int x = 0; x < n; x++) {
        for (auto [y, _, c] : g[x]) {
            // Проверяем, лежит ли ребро (x,y) на КОП s-t
            if (ds[x] + c + dt[y] == dist_st || ds[y] + c + dt[x] == dist_st) {
                ll cost = du[x] + c + dv[y];
                if (cost < ans) ans = cost;
                ll cost2 = du[y] + c + dv[x];
                if (cost2 < ans) ans = cost2;
            }
        }
    }
    
    cout << ans << '\n';
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45