Submission #1125951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125951		ardadut	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	369 ms	27260 KiB

commuter_pass

#include <bits/stdc++.h>
    
#define ll long long
#define pb push_back
#define endl "\n";
#define vec vector<ll>
#define vecvec vector<vector<ll>>
    
using namespace std;
    
/*#define FileName ""
string Ghhhh = ".in";
string Ghhhhh = ".out";
ifstream Girdi(FileName + Ghhhh);
ofstream Cikti(FileName + Ghhhhh);
#define cin Girdi
#define cout */

const ll INF = 1e15;
ll n,m,s,t,u,v;
vector<vector<pair<ll,ll>>> adj;
vector<vector<ll>> dist,dp;
vector<ll> ds;

inline void dijkstra(ll start,ll k){

    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
    pq.push({0,start});
    dist[k][start] = 0;
    
    while(!pq.empty()){
        ll node = pq.top().second;
        pq.pop();

        for(auto it : adj[node]){
            if(dist[k][it.first] > dist[k][node] + it.second){
                dist[k][it.first] = dist[k][node] + it.second;
                pq.push({dist[k][it.first],it.first});
            }
        }
    }
}

inline ll dijkstra2(ll start, ll end){

    fill(ds.begin(),ds.end(),INF);
    fill(dp[0].begin(),dp[0].end(),INF);
    fill(dp[1].begin(),dp[1].end(),INF);

    priority_queue<pair<ll,pair<ll,ll>>, vector<pair<ll,pair<ll,ll>>>, greater<pair<ll,pair<ll,ll>>>> pq;
    pq.push({0,{start,0}});

    while(!pq.empty()){
        ll node = pq.top().second.first;
        ll parent = pq.top().second.second;
        ll distt = pq.top().first;
        pq.pop();
        
        if(ds[node] == INF){
            ds[node] = distt;
            for(auto go : adj[node]){
                pq.push({ds[node] + go.second,{go.first,node}});
            } 
        }

        if(ds[node] != distt) continue;
        
        if(min(dp[0][parent],dist[0][node]) + min(dp[1][parent],dist[1][node]) <= (dp[0][node] + dp[1][node])){
            dp[0][node] = min(dp[0][parent],dist[0][node]);
            dp[1][node] = min(dp[1][parent],dist[1][node]);
        }
    }

    return dp[1][end] + dp[0][end];

}

inline void solve(){

    cin >> n >> m >> s >> t >> u >> v;
    adj.resize(n+1);
    dist.resize(2,vector<ll>(n+1,INF));
    dp.resize(2,vector<ll>(n+1));
    ds.resize(n+1);

    while(m--){
        ll a,b,w;
        cin >> a >> b >> w;
        adj[a].pb({b,w});
        adj[b].pb({a,w});
    }

    dijkstra(u,0);
    dijkstra(v,1);

    cout << min(min(dijkstra2(t,s),dijkstra2(s,t)),dist[0][v]) << endl;

}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    
}

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