Submission #1241890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241890		g4yuhg	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	2100 ms	201636 KiB

commuter_pass

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e18
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 19
#define N 100005
using namespace std;
ll n, m, s, t, x, y, d[4][N], ans = inf;
vector<pair<int, ll>> adj[N];
vector<int> adj2[N];
ll minx[N], miny[N];
bool vst[N];
void dijsktra(ll st, ll id) {
    for (int i = 1; i <= n; i ++) {
        d[id][i] = inf;
    }
    d[id][st] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({d[id][st], st});
    while (pq.size()) {
        auto c = pq.top().fi;
        auto u = pq.top().se;
        pq.pop();
        if (c > d[id][u]) continue;
        for (auto v : adj[u]) {
            if (d[id][v.fi] > c + v.se) {
                d[id][v.fi] = c + v.se;
                pq.push({c + v.se, v.fi});
            }
        }
    }
}
void trace(ll u, ll id) {
    for (auto v : adj[u]) {
        if (d[id - 0][u] + v.se + d[1 - id][v.fi] == d[0][t]) {
            adj2[u].push_back(v.fi);
            trace(v.fi, id);
        }
    }
}
void dfs2(ll u) {
    minx[u] = inf, miny[u] = inf, vst[u] = 1;
    for (auto v : adj2[u]) {
        if (vst[v]) {
            ans = min(ans, d[2][u] + miny[v]);
            ans = min(ans, d[3][u] + minx[v]);
            continue;
        }
        dfs2(v);
        ans = min(ans, d[2][u] + miny[v]);
        ans = min(ans, d[3][u] + minx[v]);
        minx[u] = min(minx[u], minx[v]);
        miny[u] = min(miny[u], miny[v]);
    }
    minx[u] = min(minx[u], d[2][u]);
    miny[u] = min(miny[u], d[3][u]);
}
signed main(void) {
    faster;
    cin >> n >> m >> s >> t >> x >> y;
    for (int i = 1; i <= m; i ++) {
        ll u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dijsktra(s, 0); dijsktra(t, 1); dijsktra(x, 2); dijsktra(y, 3);
    trace(s, 0);
    ans = d[2][y];
    dfs2(s);
    for (int i = 1; i <= n; i ++) {
        vst[i] = 0;
        adj2[i].clear();
    }
    trace(t, 1);
    dfs2(t);
    cout << ans;
    return 0;
}

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