Submission #834913

#	Time	Username	Problem	Language	Result	Execution time	Memory
834913		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	273 ms	24008 KiB

commuter_pass

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

#define task "code"
#define ll long long
#define pi pair<long long, int>

const int maxn = 1e5 + 1;

int n, m, S, T, U, V, u, v, w;
vector<pi> adj[maxn], ans;
long long d[4][maxn], mi[2][maxn], res;
priority_queue< pi, vector<pi>, greater<pi> > pq;
bool vs[maxn];

void dijktra (int p, int pr) {
    d[p][pr] = 0;
    pq.push({0, pr});

    while (!pq.empty()) {

        long long tmp = pq.top().first;
        u = pq.top().second;
        pq.pop();

        if (tmp > d[p][u]) continue;

        for (pi x : adj[u]) {
            tie(w, v) = x;

            if (d[p][v] > d[p][u] + w)
                d[p][v] = d[p][u] + w,
                pq.push({d[p][v], v});

        }
    }
}

void solve () {
    for (int i = 1; i <= n; ++ i)
        if (d[0][i] + d[1][i] == d[0][T])
            ans.emplace_back(d[0][i], i);

    sort (ans.begin(), ans.end());

    for (pi x : ans) {
        u = x.second;
        mi[0][u] = d[2][u];
        mi[1][u] = d[3][u];
        for (auto [w, v] : adj[u]) {
            if (d[0][v] + w == d[0][u])
                mi[0][u] = min(mi[0][u], mi[0][v]),
                mi[1][u] = min(mi[1][u], mi[1][v]);
        }
        res = min(res, min(mi[0][u] + d[3][u], mi[1][u] + d[2][u]));
    }
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);


    cin >> n >> m >> S >> T >> U >> V;
    for (int i = 1; i <= m; ++ i) {
        cin >> u >> v >> w;
        adj[u].push_back({w, v});
        adj[v].push_back({w, u});
    }

    memset(d, 0x3f, sizeof d);

    dijktra(0, S);
    dijktra(1, T);
    dijktra(2, U);
    dijktra(3, V);

    res = d[2][V];
    solve();

    return 0;
}

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