Submission #887668

#	Time	Username	Problem	Language	Result	Execution time	Memory
887668		noobHeMan	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	266 ms	26536 KiB

commuter_pass

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

#define int long long

const int INF = LLONG_MAX / 2;

int n, m, s, t, u, v;
const int maxN = 1e5 + 5;
vector<pair<int, int>> G[maxN];

int du[maxN], dv[maxN], ds[maxN], ans;
int dp[2][maxN];

void dijkstra1(int s, int ds[]) {
    fill(ds, ds+maxN, INF);
    ds[s] = 0;

    using T = pair<int, int>;
    priority_queue<T, vector<T>, greater<T>> pq;
    pq.push({0, s});

    while(!pq.empty()) {
        const auto [cdist, a] = pq.top(); pq.pop();
        if(cdist != ds[a]) continue;

        for(const auto &[b, w]: G[a]) {
            if(ds[a] + w < ds[b]) {
                pq.push({ds[b] = ds[a] + w, b});
            }
        }
    }
}

void dijkstra2(int s, int e) {
    fill(ds, ds+maxN, INF);
    fill(dp[0], dp[0]+maxN, INF);
    fill(dp[1], dp[1]+maxN, INF);

    ds[s] = 0;
    dp[0][s] =  du[s], dp[1][s] =  dv[s]; 

    using T = pair<int, pair<int, int>>;
    priority_queue<T, vector<T>, greater<T>> pq;
    pq.push({0, {s, 0}});

    while(!pq.empty()) {
        const auto [cdist, ap] = pq.top(); pq.pop();
        const auto [a, p] = ap;

        if(cdist != ds[a]) continue;

        for(const auto &[b, w]: G[a]) {
            int alt = ds[a] + w;
            if(alt == ds[b]) {
                if( min(dp[0][a], du[b]) + min(dp[1][a], dv[b]) <= dp[0][b] + dp[1][b] ) {
                    dp[0][b] = min(dp[0][a], du[b]);
                    dp[1][b] = min(dp[1][a], dv[b]);
                }
            } else if(alt < ds[b]) {
                dp[0][b] = min(du[b], dp[0][a]);
                dp[1][b] = min(dv[b], dp[1][a]);
                pq.push({ds[b] = alt, {b, a}});
            }
        }
    }

    ans = min(ans, dp[0][e] + dp[1][e]);
}

void solve() {
    cin >> n >> m >> s >> t >> u >> v;
    
    for(int i=0; i<m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        G[a].push_back({b, w});
        G[b].push_back({a, w});
    }

    dijkstra1(u, du);
    dijkstra1(v, dv);

    ans = du[v];

    dijkstra2(s, t);
    dijkstra2(t, s);

    cout << ans << "\n";
}

int32_t main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cout << fixed << setprecision(10);

    solve();

    return 0;
}

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