Submission #897362

#	Time	Username	Problem	Language	Result	Execution time	Memory
897362		box	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	359 ms	24932 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
    
typedef long long LL;
    
template<class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
    
const int N = 1e5;
const LL INF = 1e18;
    
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m; cin >> n >> m;
    int s, t, u, v; cin >> s >> t >> u >> v, s--, t--, u--, v--;
    static vector<pair<int, int>> g[N];
    while (m--) {
        int i, j, c; cin >> i >> j >> c, i--, j--;
        g[i].push_back({j, c}), g[j].push_back({i, c});
    }
    auto gen = [&](int s, LL *dt) {
        min_pq<pair<LL, int>> q;
        fill(dt, dt + n, INF);
        q.push({dt[s] = 0, s});
        while (!q.empty()) {
            auto [d, i] = q.top(); q.pop();
            if (d != dt[i]) continue;
            for (auto [j, c] : g[i])
                if (d + c < dt[j])
                    q.push({dt[j] = d + c, j});
        }
    };
    static LL ds[N], dt[N];
    gen(s, ds), gen(t, dt);
    static LL f[N][3];
    LL all = ds[t];
    for (int i = 0; i < n; i++) f[i][0] = f[i][1] = f[i][2] = INF;
    min_pq<tuple<LL, int, int>> q;
    q.push({f[u][0] = 0, u, 0});
    while (!q.empty()) {
        auto [d, i, t] = q.top(); q.pop();
        if (d != f[i][t]) continue;
        for (auto [j, c] : g[i]) {
            if ((t == 0 || t == 1) && ds[i] + dt[j] + c == all && d < f[j][1])
                q.push({f[j][1] = d, j, 1});
            if (t == 0 && d + c < f[j][0])
                q.push({f[j][0] = d + c, j, 0});
            if ((t == 1 || t == 2) && d + c < f[j][2])
                q.push({f[j][2] = d + c, j, 2});
        }
    }
    LL tmp = min({f[v][0], f[v][1], f[v][2]});
    for (int i = 0; i < n; i++) f[i][0] = f[i][1] = f[i][2] = INF;
    q.push({f[u][0] = 0, u, 0});
    while (!q.empty()) {
        auto [d, i, t] = q.top(); q.pop();
        if (d != f[i][t]) continue;
        for (auto [j, c] : g[i]) {
            if ((t == 0 || t == 1) && dt[i] + ds[j] + c == all && d < f[j][1])
                q.push({f[j][1] = d, j, 1});
            if (t == 0 && d + c < f[j][0])
                q.push({f[j][0] = d + c, j, 0});
            if ((t == 1 || t == 2) && d + c < f[j][2])
                q.push({f[j][2] = d + c, j, 2});
        }
    }
    tmp = min(tmp, min({f[v][0], f[v][1], f[v][2]}));
    cout << tmp << '\n';
    return 0;
}

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