Submission #833883

#	Time	Username	Problem	Language	Result	Execution time	Memory
833883		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	305 ms	32292 KiB

commuter_pass

#include <bits/stdc++.h>

using ll = long long;
const int nmax = 5e5 + 5;
const int mod = 1e9 + 7;
const int M = nmax * nmax + 5;
const ll oo = 1e18;
const int lg = 20;
#define fi first
#define se second
#define pii pair<ll, ll>
using namespace std;

int n, m, S, T, U, V;
priority_queue<pii, vector<pii>, greater<pii>> q;
ll dp[nmax][4], f[nmax], ans = oo;
pii a[nmax];
vector<pii> adj[nmax];

void build(int S, int x){
    for(int i = 1; i <= n; ++i) dp[i][x] = oo;
    dp[S][x] = 0;
    q.push({0, S});
    while(q.size()){
        int u = q.top().se;
        int lc = q.top().fi;
        q.pop();
        if(dp[u][x] != lc) continue;
        for(auto [w, v] : adj[u]){
            if(dp[v][x] > dp[u][x] + w){
                dp[v][x] = dp[u][x] + w;
                q.push({dp[v][x], v});
            }
        }
    }
}

void sol(){
    for(int i = 1; i <= n; ++i) a[i] = {dp[i][0], i};
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; ++i) f[i] = dp[i][2];
    for(int i = n; i >= 1; --i){
        int u = a[i].se;
        for(auto [w, v] : adj[u]){
            if(dp[u][0] + w == dp[v][0] && dp[v][0] + dp[v][3] == dp[T][0]){
                f[u] = min(f[u], f[v]);
            }
        }
    }
    for(int i = 1; i <= n; ++i) ans = min(ans, f[i] + dp[i][1]);
    for(int i = 1; i <= n; ++i) f[i] = dp[i][1];
     for(int i = n; i >= 1; --i){
        int u = a[i].se;
        for(auto [w, v] : adj[u]){
            if(dp[u][0] + w == dp[v][0] && dp[v][0] + dp[v][3] == dp[T][0]){
                f[u] = min(f[u], f[v]);
            }
        }
    }
    for(int i = 1; i <= n; ++i) ans = min(ans, f[i] + dp[i][2]);
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    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({w, v});
        adj[v].push_back({w, u});
    }
    build(S, 0);
    build(U, 1);
    build(V, 2);
    build(T, 3);
    sol();
}
/*

*/

Compilation message (stderr)

commuter_pass.cpp:6:20: warning: integer overflow in expression of type 'int' results in '896896857' [-Woverflow]
    6 | const int M = nmax * nmax + 5;
      |               ~~~~~^~~~~~

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