Submission #1129824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129824		Sofiatpc	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	375 ms	24812 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define sc second
#define sz(v) (int)v.size()
typedef long long ll;
const int MAXN = 1e5+5;
const ll INF = 1e17+5;
vector< pair<int,int> > adj[MAXN];
int marc[MAXN];
ll inid[MAXN], d[4][MAXN];

void dfs(int s){
    marc[s] = 1;
    for(int i = 0; i < sz(adj[s]); i++){
        int viz = adj[s][i].fi; ll p = adj[s][i].sc;
            
        if(!marc[viz] && inid[viz] + p == inid[s])dfs(viz);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n,m,S,T,U,V; cin>>n>>m>>S>>T>>U>>V;
    for(int i = 1; i <= m; i++){
        int a,b,c; cin>>a>>b>>c;
        adj[a].emplace_back(b,c);
        adj[b].emplace_back(a,c);
    }

    for(int i = 1; i <= n; i++){
        inid[i] = INF;
        d[0][i] = INF; d[1][i] = INF; d[2][i] = INF; d[3][i] = INF;
    }

    set< pair<ll,int> > st;
    inid[S] = 0;
    st.insert({0,S});
    while(sz(st) > 0){
        int s = st.begin()->sc; st.erase(st.begin());

        for(int i = 0; i < sz(adj[s]); i++){
            int viz = adj[s][i].fi; ll p = adj[s][i].sc;
            if(inid[viz] > inid[s]+p){
                st.erase({inid[viz],viz});
                inid[viz] = inid[s] + p;
                st.insert({inid[viz],viz});
            }
        }
    }

    dfs(T);

    set< pair<ll, pair<int,int>>> st2;
    d[0][U] = 0;
    st2.insert({0, {0,U}});

    while(sz(st2) > 0){
        int e = st2.begin()->sc.fi, s = st2.begin()->sc.sc; st2.erase(st2.begin());

        for(int i = 0; i < sz(adj[s]); i++){
            int viz = adj[s][i].fi; ll p = adj[s][i].sc;

            if(e == 0){
                if(d[0][viz] > d[0][s] + p){
                    st2.erase({d[0][viz], {0,viz}});
                    d[0][viz] = d[0][s] + p;
                    st2.insert({d[0][viz], {0,viz}});
                }

                if(marc[viz] && marc[s]){
                    if(inid[viz] == inid[s] + p && d[1][viz] > d[0][s]){
                        st2.erase({d[1][viz], {1,viz}});
                        d[1][viz] = d[0][s];
                        st2.insert({d[1][viz], {1,viz}});
                    }
                    if(inid[viz] == inid[s] - p && d[2][viz] > d[0][s]){
                        st2.erase({d[2][viz], {2,viz}});
                        d[2][viz] = d[0][s];
                        st2.insert({d[2][viz], {2,viz}});
                    }
                }

            }else if(e == 1){
                if(d[3][viz] > d[1][s] + p){
                    st2.erase({d[3][viz], {3,viz}});
                    d[3][viz] = d[1][s] + p;
                    st2.insert({d[3][viz], {3,viz}});
                }

                if(marc[viz] && inid[viz] == inid[s] + p && d[1][viz] > d[1][s]){
                    st2.erase({d[1][viz], {1,viz}});
                    d[1][viz] = d[1][s];
                    st2.insert({d[1][viz], {1,viz}});
                }

            }else if(e == 2){
                if(d[3][viz] > d[2][s] + p){
                    st2.erase({d[3][viz], {3,viz}});
                    d[3][viz] = d[2][s] + p;
                    st2.insert({d[3][viz], {3,viz}});
                }

                if(marc[viz] && inid[viz] == inid[s] - p && d[2][viz] > d[2][s]){
                    st2.erase({d[2][viz], {2,viz}});
                    d[2][viz] = d[2][s];
                    st2.insert({d[2][viz], {2,viz}});
                }

            }else if(d[3][viz] > d[3][s] + p){
                st2.erase({d[3][viz], {3,viz}});
                d[3][viz] = d[3][s] + p;
                st2.insert({d[3][viz], {3,viz}});
            }
        }
    }

    cout<<min({ d[0][V], d[1][V], d[2][V], d[3][V] })<<"\n";
}

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