Submission #1103160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103160		coolboy19521	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	497 ms	25416 KiB

commuter_pass

#include "bits/stdc++.h"

typedef long long ll;
using namespace std;

const ll inf = 1e18 + 18;

int main() {
    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;

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

    for (int i = 1; i <= m; i ++) {
        int a, b, c;
        cin >> a >> b >> c;

        aj[a].emplace_back(b, c);
        aj[b].emplace_back(a, c);
    }

    auto dij = [&aj,n](int u, auto& ds){
        priority_queue<pair<ll,int>> pq;
        vector<bool> vi(n + 1);
        
        pq.emplace(0, u);

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

            if (!vi[v]) {
                vi[v] = true;
                ds[v] = -w;

                for (auto& [b, c] : aj[v]) {
                    pq.emplace(w - c, b);
                }
            }
        }
    };


    vector<ll> dsu(n + 1), dsv(n + 1);
    dij(u, dsu);
    dij(v, dsv);

    auto go = [&dsu,&dsv,&aj,n](int u, int v){
        vector<ll> dpu(n + 1, inf), dpv(n + 1, inf);
        priority_queue<tuple<ll,int,int>> pq;
        vector<bool> vi(n + 1);
        vector<ll> ds(n + 1);

        pq.emplace(0, u, 0);

        while (!pq.empty()) {
            auto [w, a, p] = pq.top();
            pq.pop();

            if (!vi[a]) {
                vi[a] = true;
                ds[a] = w;

                dpu[a] = min(dpu[p], dsu[a]);
                dpv[a] = min(dpv[p], dsv[a]);

                for (auto& [b, c] : aj[a]) {
                    pq.emplace(w - c, b, a);
                }
            } else if (w == ds[a]) {
                if (min(dsu[a], dpu[p]) + min(dsv[a], dpv[p]) <= dpu[a] + dpv[a]) {
                    dpu[a] = min(dpu[p], dsu[a]);
                    dpv[a] = min(dpv[p], dsv[a]);
                }
            }
        }

        return dpu[v] + dpv[v];
    };

    cout << min({dsu[v], go(s, t), go(t, s)}) << '\n';
}

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