Submission #1085709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085709		thaibeo123	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	166 ms	22272 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fi first
#define se second
const int N = 1e5 + 5;
int n, m, s, t, x, y;
ll dx[N], dy[N], ans, dp[N][2], ds[N];
vector<pair<int, int>> g[N];
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
void dijkstra1(int u, ll d[]) {
    for (int i = 1; i <= n; ++i) d[i] = 1e18;
    d[u] = 0;
    pq.push({d[u], u});
    while (!pq.empty()){
        int u = pq.top().se;
        ll cost = pq.top().fi;
        pq.pop();
        if (cost > d[u]) continue;
        for (pair<int, int> b : g[u]) {
            int v = b.fi;
            ll w = b.se;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }
}
void dijkstra2(int S) {
    for (int i = 1; i <= n; ++i) {
        dp[i][0] = dp[i][1] = 1e18;
        ds[i] = 1e18;
    }
    ds[S] = 0;
    dp[S][0] = dx[S];
    dp[S][1] = dy[S];
    pq.push({ds[S], S});
    while (!pq.empty()) {
        int u = pq.top().se;
        ll cost = pq.top().fi;
        pq.pop();
        if (cost > ds[u]) continue;
        for (pair<int, int> b : g[u]) {
            int v = b.fi;
            ll w = b.se;
            if (ds[v] > ds[u] + w) {
                ds[v] = ds[u] + w;
                dp[v][0] = min(dx[v], dp[u][0]);
                dp[v][1] = min(dy[v], dp[u][1]);
                pq.push({ds[v], v});
            }
            else if (ds[v] == ds[u] + w) {
                dp[v][0] = min(dp[v][0], dp[u][0]);
                dp[v][1] = min(dp[v][1], dp[u][1]);
            }
        }
    }
    ans = min(ans, dp[t][0] + dp[t][1]);
}
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> s >> t >> x >> y;
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    dijkstra1(x, dx);
    dijkstra1(y, dy);
    ans = dx[y];
    dijkstra2(s);
    cout << ans;
    return 0;
}

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