Submission #1082876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082876		bundaunuoctuong	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	160 ms	20364 KiB

commuter_pass

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

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

int n, m, s, t, U, V;
vector<pair<int, int>> adj[N];
ll dis[2][N], ans, dp[2][N], d[N];
bool vst[N];

void dij1(int st, int id) {
    for (int i = 1; i <= n; i++) {
        dis[id][i] = INF;
        vst[i] = false;
    }
    dis[id][st] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
    q.push({0, st});
    
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vst[u]) continue;
        vst[u] = true;
        
        for (auto it : adj[u]) {
            int v = it.first;
            int w = it.second;
            if (dis[id][v] > dis[id][u] + w) {
                dis[id][v] = dis[id][u] + w;
                q.push({dis[id][v], v});
            }
        }
    }
}

void dij2(int st, int en) {
    for (int i = 0; i <= n; i++) {
        vst[i] = false;
        dp[0][i] = dp[1][i] = INF;
        d[i] = INF;
    }
    
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
    d[st] = 0;
    q.push({0, st});
    dp[0][st] = dis[0][st];
    dp[1][st] = dis[1][st];
    
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vst[u]) continue;
        vst[u] = true;
        
        for (auto it : adj[u]) {
            int v = it.first;
            int w = it.second;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                dp[0][v] = min(dis[0][v], dp[0][u]);
                dp[1][v] = min(dis[1][v], dp[1][u]);
                q.push({d[v], v});
            } else if (d[v] == d[u] + w) {
                if (min(dis[0][v], dp[0][u]) + min(dis[1][v], dp[1][u]) < dp[0][v] + dp[1][v]) {
                    dp[0][v] = min(dis[0][v], dp[0][u]);
                    dp[1][v] = min(dis[1][v], dp[1][u]);
                }
            }
        }
    }
    ans = min(ans, dp[0][en] + dp[1][en]);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> s >> t >> U >> V;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dij1(U, 0);
    dij1(V, 1);
    ans = dis[0][V];
    dij2(s, t);
    if (ans != INF) cout << ans;
    else cout << -1;
    return 0;
}

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