제출 #1147382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147382		dobri_oke	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	134 ms	57436 KiB

commuter_pass

//#pragma GCC target ("avx2")   
//#pragma GCC optimize ("Ofast")   
#include <bits/stdc++.h>   
using namespace std;  
#define int long long  
#define F first 
#define S second 
#define pb push_back 
const int N = 1e6, NN=10;
const int mod=1e9+7;

vector < pair < int, int > > vr[N], vr2[N];

vector < int > top;

bool was[N], was2[N];

int n, m, s, t, u, v;

int d1[N], d2[N], dp[3][N], d[N];

void dfs(int x){
    was[x]=1;
    for(auto to : vr2[x]){
        if(was[to.F]) continue;
        dfs(to.F);
    }
    top.pb(x);
}

void dfs2(int x){
    was2[x]=1;
    for(auto to : vr[x]){
        if(was2[to.F]) continue;
        if(d[to.F]+to.S==d[x]){
            vr2[to.F].pb({x, 0});
            dfs2(to.F);
        }
    }
}

void dj1(int x){
    multiset < pair < int, int > > st;
    st.insert({0, x});
    for(int i=1;i<=n;i++){ 
        d1[i]=1e18;  
    }
    d1[x]=0;
    while(st.size()>0){
        int f1=(*st.begin()).F, s1=(*st.begin()).S;
        st.erase(st.find({f1, s1}));
        for(auto to : vr[s1]){
            int f2=to.F, s2=to.S;
            if(d1[f2]>d1[s1]+s2){
                st.erase({d1[f2], f2});
                d1[f2]=d1[s1]+s2;
                st.insert({d1[f2], f2});
            }
        }
    }
    dfs2(t);
}

void dj2(int x){
    multiset < pair < int, int > > st;
    st.insert({0, x});
    for(int i=1;i<=n;i++) d2[i]=1e18;
    d2[x]=0;
    while(st.size()>0){
        int f1=(*st.begin()).F, s1=(*st.begin()).S;
        st.erase(st.find({f1, s1}));
        for(auto to : vr[s1]){
            int f2=to.F, s2=to.S;
            if(d2[f2]>d2[s1]+s2){
                st.erase({d2[f2], f2});
                d2[f2]=d2[s1]+s2;
                st.insert({d2[f2], f2});
            }
        }
    }
}

void dj(){
    multiset < pair < int, int > > st;
    st.insert({0, s});
    for(int i=1;i<=n;i++){ 
        d[i]=1e18;  
    }
    d[s]=0;
    while(st.size()>0){
        int f1=(*st.begin()).F, s1=(*st.begin()).S;
        st.erase(st.find({f1, s1}));
        for(auto to : vr[s1]){
            int f2=to.F, s2=to.S;
            if(d[f2]>d[s1]+s2){
                st.erase({d[f2], f2});
                d[f2]=d[s1]+s2;
                st.insert({d[f2], f2});
            }
        }
    }
    dfs2(t);
}
//int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b); }
//int lcm(int a, int b) { return a / gcd(a, b) * b; }
//int binpow(int a,int b){if(!b)return 1; if(b&1)return a*binpow(a,b-1)%mod; int x=binpow(a,b/2); return x*x%mod;}
signed main(){   
    ios_base::sync_with_stdio(0);   
    cin.tie(0);   
    cout.tie(0);
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;
    
    for(int i=1;i<=n;i++){
        int a, b, c;
        cin >> a >> b >> c;
        vr[a].pb({b, c});
        vr[b].pb({a, c});
    }
    
    dj1(u);
    dj2(v);
    dj();
    dfs(s);
    
    for(int i=1;i<=n;i++){
        dp[1][i]=1e18;
        dp[2][i]=1e18;
    }
    
    int ans=d1[v];
    
    for(auto to : top){
        ans=min(ans, d1[to]+d2[to]);
        dp[1][to]=d2[to];
        dp[2][to]=d1[to];
        for(auto to2 : vr2[to]){
            dp[1][to]=min(dp[1][to], dp[1][to2.F]);
            dp[2][to]=min(dp[2][to], dp[2][to2.F]);
            ans=min({ans, dp[1][to]+d1[to], dp[2][to]+d2[to]});
        }
    }
    cout << ans;
}

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