제출 #1013981

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1013981		Otalp	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	781 ms	61780 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define int ll
#define mp make_pair

vector<pii> q[200100], dq[200100];
int us[200100], dp[200100], bd[200100], pos[200100], ddp[200100][4], dus[200100][4];
pii d1, d2;

int dfs(int v){
    if(v == d1.ss){
        bd[v] = 1;
    }
    pos[v] = 1;
    for(pii h: q[v]){
        int to = h.ff;
        int x = h.ss;
        if(dp[to] != dp[v] + x) continue;
        if(!pos[to] and dp[to] == dp[v] + x) dfs(to);
        bd[v] |= bd[to];
    }
    return bd[v];
}
 
 
void solve(){
    int n, m;
    cin>>n>>m;
    cin>>d1.ff>>d1.ss;
    cin>>d2.ff>>d2.ss;
    for(int i=1; i<=m; i++){
        int l, r, x;
        cin>>l>>r>>x;
        q[l].pb({r, x});
        q[r].pb({l, x});
    }
    set<pii> d;
    d.insert({0, d1.ff});
    while(d.size()){
        auto it =  *d.begin();
        int v = it.ss;
        if(us[v]){
            d.erase(d.find(it));
            continue;
        }
        us[v] = 1;
        dp[v] = it.ff;
        for(pii h: q[v]){
            int to = h.ff;
            int x = h.ss;
            if(us[to]) continue;
            d.insert({dp[v] + x, to});
        }
    }
    dfs(d1.ff);
    set<pair<pii, int>> dd;
    for(int i=1; i<=n; i++) us[i] = 0;
    dd.insert(mp(mp(0, 0), d2.ff));
    while(dd.size()){
        auto it =  *dd.begin();
        int v = it.ss;
        int f = it.ff.ss;
        if(dus[v][f]){
            dd.erase(dd.find(it));
            continue;
        }
        //cout<<it.ff.ff<<' '<<it.ff.ss<<' '<<it.ss<<'\n';
        dus[v][f] = 1;
        ddp[v][f] = it.ff.ff;
        if(f == 0){
            for(pii h: q[v]){
                int to = h.ff;
                int x = h.ss;
                if(dus[to][1]) continue;
                if(bd[v] and bd[to] and dp[to] == dp[v] + x) dd.insert(mp(mp(ddp[v][f], 1), to));
            }
            for(pii h: q[v]){
                int to = h.ff;
                int x = h.ss;
                if(dus[to][2]) continue;
                if(bd[v] and bd[to] and dp[v] == dp[to] + x) dd.insert(mp(mp(ddp[v][f], 2), to));
            }
            for(pii h: q[v]){
                int to = h.ff;
                int x = h.ss;
                if(dus[to][0]) continue;
                dd.insert(mp(mp(ddp[v][f] + x, 0), to));
            }
        }
        if(f == 1){
            for(pii h: q[v]){
                int to = h.ff;
                int x = h.ss;
                if(dus[to][1]) continue;
                if(bd[v] and bd[to] and dp[to] == dp[v] + x) dd.insert(mp(mp(ddp[v][f], 1), to));
            }
            for(pii h: q[v]){
                int to = h.ff;
                int x = h.ss;
                if(dus[to][3]) continue;
                dd.insert(mp(mp(ddp[v][f] + x, 3), to));
            }
        }
        if(f == 2){
            for(pii h: q[v]){
                int to = h.ff;
                int x = h.ss;
                if(dus[to][2]) continue;
                if(bd[v] and bd[to] and dp[v] == dp[to] + x) dd.insert(mp(mp(ddp[v][f], 2), to));
            }
            for(pii h: q[v]){
                int to = h.ff;
                int x = h.ss;
                if(dus[to][3]) continue;
                dd.insert(mp(mp(ddp[v][f] + x, 3), to));
            }
        }
        if(f == 3){
            for(pii h: q[v]){
                int to = h.ff;
                int x = h.ss;
                if(dus[to][3]) continue;
                dd.insert(mp(mp(ddp[v][f] + x, 3), to));
            }
        }
    }
    int ans = 1e18;
    for(int i=0; i<4; i++){
        if(!dus[d2.ss][i]) continue;
        ans = min(ans, ddp[d2.ss][i]);
    }
    cout<<ans<<'\n';
}
    
 
signed main(){
    solve();
}

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