Submission #1173938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173938		khoile08	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	269 ms	54304 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FOD(i, a, b) for(int i = a; i >= b; i--)
#define int long long
#define fi first
#define se second
#define ll long long
#define ii pair<int,int>
#define pb push_back
#define sq(a) (a) * (a)

const int N = 1e5 + 5;
const ll INF = 1e18;

int n, m, s, t, x, y;
vector<ii> g[N], ng[3*N];
ll d[2][3*N];

void Dijk(int beg, int t) {
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    pq.push({0, beg});
    FOR(i, 1, n) d[t][i] = INF;
    d[t][beg] = 0;
    while(!pq.empty()) {
        ll cost = pq.top().fi;
        int u = pq.top().se;
        pq.pop();
        if(cost > d[t][u]) continue;
        for(ii H : g[u]) {
            int v = H.fi;
            int l = H.se;
            if(d[t][v] > d[t][u] + l) {
                d[t][v] = d[t][u] + l;
                pq.push({d[t][v], v});
            }
        }
    }
}

void Dijk2(int beg, int t) {
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    pq.push({0, beg});
    FOR(i, 1, 3 * n) d[t][i] = INF;
    d[t][beg] = 0;
    while(!pq.empty()) {
        ll cost = pq.top().fi;
        int u = pq.top().se;
        pq.pop();
        if(cost > d[t][u]) continue;
        for(ii H : ng[u]) {
            int v = H.fi;
            int l = H.se;
            if(d[t][v] > d[t][u] + l) {
                d[t][v] = d[t][u] + l;
                pq.push({d[t][v], v});
            }
        }
    }
}

signed main() {
//    freopen("khoile.inp", "r", stdin);
//    freopen("khoile.out", "w", stdout);

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m >> s >> t >> x >> y;
    FOR(i, 1, m) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }

    Dijk(s, 0);
    Dijk(t, 1);

    FOR(u, 1, n) {
        ng[u].pb({u + n, 0});
        ng[u + n].pb({u + 2 * n, 0});
        for(ii H : g[u]) {
            int v = H.fi;
            ll w = H.se;
            if(d[0][t] == d[0][u] + d[1][v] + w || d[0][t] == d[0][v] + d[1][u] + w) {
                ng[u + n].pb({v + n, 0});
            }
            ng[u].pb({v, w});
            ng[u + 2 * n].pb({v + 2 * n, w});
        }
    }

    Dijk2(x, 0);
    cout << min(d[0][y], d[0][y + 2 * n]);
}

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