Submission #667212

#	Time	Username	Problem	Language	Result	Execution time	Memory
667212		smirichto	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	388 ms	38456 KiB

commuter_pass

/*
    STAY ORGANIZED
    CHANGE YOUR APPROACH
    BE CONFIDENT
    WA , WHATEVER STAY CALM
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
typedef long double ld ;
#define FAST ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
#define pb push_back
#define pi pair<ll,ll>
#define pll pair<ll,ll>
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define flag cout<<"hi"<<endl;
#define fr(i,a,b) for(ll i = a;i < (ll)b;i++)
#define rfr(i,a,b) for(ll i = a;i > (ll)b;i--)
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define alll(x) ((x).begin()+1), (x).end()
#define MOD mod
#define endl '\n'
const ll mod = 1e9+7 ;
void io(){ios::sync_with_stdio(false) ;cin.tie(NULL) ;//freopen("grader.in.4","r",stdin) ;freopen("grader.out.4","w",stdout) ;
}
void dbg(vector<ll> tab){for(auto it : tab) cout<<it<<" ";cout<<endl;}
void dbgg(pi p){cout<<p.F<<" "<<p.S<<endl;}
void dbgpi(vector<pi> tab){for(auto it : tab) dbgg(it) ;}
template<class T> bool ckmax(T& a, const T& b){return a < b ? a = b, 1 : 0;}
template<class T> bool ckmin(T& a, const T& b){return a > b ? a = b, 1 : 0;}
template<class T> void add(T& a, const T& b){a = a + b ; if(a>mod) a-= mod ;}
void nop(){cout<<-1<<endl;return;}
const ll N = 1e5 +5 ;
const ll inf = 1e17 ;
ll n , m , x , y , s , t  ;
vector<pi> v[N]  ;
vector<ll> dag[N] , par[N] ;
map<ll , bool> aded[N] ;
ll distf[N][5] ;

void dijkstra(ll source ,ll k)
{
    for(ll i = 1 ; i<=n ; i++){
        distf[i][k] = inf ;
    }
    distf[source][k] = 0 ;
    priority_queue<pi , vector<pi> , greater<pi>> pq ;
    vector<ll> vis(n+1 , 0) ;
    distf[source][k] = 0 ;
    pq.push({0 , source}) ;
    while(!pq.empty()){
        auto [d , node] = pq.top() ;
        pq.pop() ;
        if(vis[node]) continue ;
        vis[node] = 1 ;
        for(auto [to , w] : v[node]){
            if(w + d < distf[to][k]){
                distf[to][k] = w + d ;
                pq.push({distf[to][k] , to}) ;
            }
        }
    }

}

void solve()
{
    cin>>n>>m>>s>>t>>x>>y ;
    for(ll i = 1 ; i<=m ; i++){
        ll from , to , weight ;
        cin>>from>>to>>weight ;
        v[from].pb({to , weight}) ;
        v[to].pb({from , weight}) ;
    }
    priority_queue<pi , vector<pi> , greater<pi>> pq ;
    vector<ll> dist(n+1 , inf) ;
    vector<ll> vis(n+1 , 0) , ind(n+1,0) ;
    dist[s] = 0 ;
    pq.push({0 , s}) ;
    while(!pq.empty()){
        auto [d , node] = pq.top() ;
        pq.pop() ;
        if(vis[node]) continue ;
        vis[node] = 1 ;
        for(auto [to , w] : v[node]){
            if(w + d < dist[to]){
                dist[to] = w + d ;
                pq.push({dist[to] , to}) ;
                par[to].clear() ;
                par[to].pb(node) ;
                ind[to] = 1 ;
            }
            else if (d + w == dist[to]){
                par[to].pb(node) ;
                ind[to]++ ;
            }
        }
    }
    dijkstra(x , 1) ;
    dijkstra(y , 2) ;

    queue<ll> q ;
    vector<ll> order ;
    for(ll i = 1 ; i<=n ; i++){
       for(auto it : par[i]){
            dag[it].pb(i) ;
       }
    }

    for(ll i = 1 ; i<=n ; i++){
        if(!ind[i]) q.push(i) ;
    }

    while(!q.empty()){
        ll node = q.front() ;
        q.pop() ;
        order.pb(node) ;
        for(auto it : dag[node]){
            ind[it]-- ;
            if(!ind[it]) q.push(it) ;
        }
    }
    vector<ll> dist1(n+1 , inf) , dist2(n+1 , inf) ;

    for(ll node : order){
        dist1[node] = min(dist1[node] , distf[node][1]) ;
        dist2[node] = min(dist2[node] , distf[node][2]) ;
        for(auto to : dag[node]){
            if(min(dist1[node] , distf[to][1]) + min(dist2[node] , distf[to][2]) <dist1[to] + dist2[to] ){
                dist1[to] = min(dist1[node] , distf[to][1]) ;
                dist2[to] = min(dist2[node] , distf[to][2]) ;
            }
        }
    }
    cout<<min(distf[y][1] , dist1[t] + dist2[t])<<endl;


}

int main()
{
    /*
        UNORDERED MAP IS SHIT
        NEVER USE IT AGAIN
    */
    io() ;
    ll tt = 1 ;
//    cin>>tt ;
    while(tt--) solve() ;
    return 0 ;
}

/*
    !!!
        ARRAY BOUNDS
        OVERFLOW
        UNORDERED MAP
        CEIL DIV ON NEGATIVES
*/

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