Submission #1166193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166193		altern23	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	180 ms	24520 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const ll N = 2e5;
const ll INF = 4e18;
const ll MOD = 1e9 + 7;

ll dp1[N + 5], dp2[N + 5], dp3[N + 5], dp4[N + 5], dp5[N + 5];
bool vis[N + 5];

vector<pii> adj[N + 5];

/*
dp1 -> dari s
dp2 -> dari u
dp3 -> dari v
dp4 dan dp5 -> calc
*/

ll ans = INF;

void dfs(ll idx){
    dp4[idx] = dp2[idx];
    dp5[idx] = dp3[idx];
    for(auto [i, j] : adj[idx]){
        if(!vis[i] && dp1[i] + j == dp1[idx]){
            vis[i] = 1;
            dfs(i);
            dp4[idx] = min(dp4[idx], dp4[i]);
            dp5[idx] = min(dp5[idx], dp5[i]);
        }
    }
    ans = min(ans, dp3[idx] + dp4[idx]);
    ans = min(ans, dp2[idx] + dp5[idx]);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll n, m; cin >> n >> m;
        ll s, t; cin >> s >> t;
        ll u, v; cin >> u >> v;

        for(int i = 1; i <= n; i++){
            dp1[i] = dp2[i] = dp3[i] = dp4[i] = dp5[i] = INF;
        }

        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});
        }

        dp1[s] = 0;
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        pq.push({0, s});
        for(;!pq.empty();){
            auto [dist, idx] = pq.top(); pq.pop();
            if(dist > dp1[idx]) continue;
            for(auto [i, j] : adj[idx]){
                if(dp1[i] > dist + j){
                    dp1[i] = dist + j;
                    pq.push({dp1[i], i});
                }
            }
        }
        
        dp2[u] = 0;
        pq.push({0, u});
        for(;!pq.empty();){
            auto [dist, idx] = pq.top(); pq.pop();
            if(dist > dp2[idx]) continue;
            for(auto [i, j] : adj[idx]){
                if(dp2[i] > dist + j){
                    dp2[i] = dist + j;
                    pq.push({dp2[i], i});
                }
            }
        }

        dp3[v] = 0;
        pq.push({0, v});
        for(;!pq.empty();){
            auto [dist, idx] = pq.top(); pq.pop();
            if(dist > dp3[idx]) continue;
            for(auto [i, j] : adj[idx]){
                if(dp3[i] > dist + j){
                    dp3[i] = dist + j;
                    pq.push({dp3[i], i});
                }
            }
        }

        ans = dp2[v];
        dfs(t);

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

/*

*/ 

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