Submission #377201

#	Time	Username	Problem	Language	Result	Execution time	Memory
377201		smjleo	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	376 ms	20192 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define nl '\n'
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
const int mod = 1000000007, mod2 = 998244353;

// change this
const int N = 100005;

int n, m, s, t, u, v, du[N], dv[N], ds[N], dt[N], b1[N], b2[N];
vector< pair<int, int> > g[N];

signed main() {
    io;
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;

    for (int i=0; i<m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    // distance from u
    priority_queue< pair<int, int>, vector<pair<int, int> >, greater<> > pq;
    for (int i=1; i<=n; i++) du[i] = dv[i] = ds[i] = dt[i] = b1[i] = b2[i] = 1e18;

    du[u] = 0;
    pq.push({0, u});

    while (!pq.empty()) {
        auto cur = pq.top();
        pq.pop();
        int x = cur.second, d = cur.first;

        if (d > du[x]) continue;

        for (auto i : g[x]) {
            int nx = i.first, nd = d + i.second;
            // cout << "AA " << x << ' ' <<  nx << ' ' << nd << nl;
            if (du[nx] <= nd) continue;
            du[nx] = nd;
            pq.push({nd, nx});
        }
    }

    // distance from v
    dv[v] = 0;
    pq.push({0, v});

    while (!pq.empty()) {
        auto cur = pq.top();
        pq.pop();

        int x = cur.second, d = cur.first;
        if (d > dv[x]) continue;

        for (auto i : g[x]) {
            int nx = i.first, nd = d + i.second;
            if (dv[nx] <= nd) continue;
            dv[nx] = nd;
            pq.push({nd, nx});
        }
    }

    // distance from s, update b1[N] also
    ds[s] = 0;
    b1[s] = dv[s];
    pq.push({0, s});

    while (!pq.empty()) {
        auto cur = pq.top();
        pq.pop();

        int x = cur.second, d = cur.first;
        if (d > ds[x]) continue;

        for (auto i : g[x]) {
            int nx = i.first, nd = d + i.second;
            if (ds[nx] <= nd) continue;
            ds[nx] = nd;
            b1[nx] = min(b1[nx], min(dv[nx], b1[x]));
            pq.push({nd, nx});
        }
    }

    // distance from t, update b2[N] also
    dt[t] = 0;
    b2[t] = dv[t];
    pq.push({0, t});

    while (!pq.empty()) {
        auto cur = pq.top();
        pq.pop();

        int x = cur.second, d = cur.first;
        if (d > dt[x]) continue;

        for (auto i : g[x]) {
            int nx = i.first, nd = d + i.second;
            if (dt[nx] <= nd) continue;
            dt[nx] = nd;
            b2[nx] = min(b2[nx], min(dv[nx], b2[x]));
            pq.push({nd, nx});
        }
    }

    int ans = du[v];

    // for (int i=1; i<=n; i++) cout << du[i] << ' ';
    // cout << nl;

    for (int i=1; i<=n; i++) {
        // is it on the shortest path?
        if (ds[i] + dt[i] != ds[t]) continue;   // no!
        ans = min(ans, 
            du[i] +     // go here first
            min(b1[i], b2[i])  // go to destination
        );
    }

    cout << ans << nl;
}

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