Submission #1264328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264328		avohado	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	296 ms	30128 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define maxn 200005
#define f first
#define s second
#define ll long long
#define pb(x) push_back(x)
#define mp make_pair
int n, m, s, t, u1, v1, l[maxn], used[maxn];
long long fp[maxn], pth[maxn][4];
vector<pair<int, int>> g[maxn];
bool check(int u, int v, int r, int j){
    if(r){
        return (fp[v]+l[j]==fp[u]);
    }else{
        return (fp[u]+l[j]==fp[v]);
    }
}
void solve(){
    cin >> n >> m >> s >> t >> u1 >> v1;
    for(int i=0; i<m; i++){
        int u, v;
        cin >> u >> v >> l[i];
        g[u].pb(mp(v, i));
        g[v].pb(mp(u, i));
    }
    for(int i=0; i<=n; i++){
        fp[i]=INT64_MAX;
        for(int j=0; j<4; j++){
            pth[i][j]=fp[i];
        }
    }
    set<pair<int, long long>> st;
    st.insert({0, s});
    fp[s]=0;
    while(fp[t]>(*st.begin()).f){
        int u=(*st.begin()).s;long long w=(*st.begin()).f;
        st.erase(st.begin());
        if(fp[u]<w){
            continue;
        }
        for(auto v:g[u]){
            if(fp[v.f]>w+l[v.s]){
                fp[v.f]=w+l[v.s];
                st.insert(mp( fp[v.f],v.f));
            }
        }
    }
    queue<int> q;
    q.push(t);
    used[t]=1;
    while(q.size()){
        int u=q.front(); q.pop();
        for(auto v:g[u]){
            if(fp[v.f]+l[v.s]==fp[u]&&!used[v.f]){
                used[v.f]=1;
                q.push(v.f);
            }
        }
    }
    set<pair<long long, pair<int, int>>> st1;
    st1.insert({0, {u1, 2}});
    pth[u1][2]=pth[u1][1]=pth[u1][0]=0;
    if(used[u1]){
        st1.insert({0, {u1, 0}});
        st1.insert({0, {u1, 1}});
    }
    while((*st1.begin()).f<min({pth[v1][0],pth[v1][1],pth[v1][2],pth[v1][3]})){
        pair<long long,pair<int, int>> u=(*st1.begin());st1.erase(st1.begin());
        if(pth[u.s.f][u.s.s]<u.f){
            continue;
        }
        if(u.s.s>1){
            for(auto v:g[u.s.f]){
                if(pth[v.f][u.s.s]>u.f+l[v.s]){
                    pth[v.f][u.s.s]=u.f+l[v.s];
                    st1.insert({u.f+l[v.s], {v.f, u.s.s}});
                }
                if(u.s.s==2&&used[v.f]){
                    if(pth[v.f][0]>u.f+l[v.s]){
                        pth[v.f][0]=u.f+l[v.s];
                        st1.insert({u.f+l[v.s], {v.f, 0}});
                    }
                    if(pth[v.f][1]>u.f+l[v.s]){
                        pth[v.f][1]=u.f+l[v.s];
                        st1.insert({u.f+l[v.s], {v.f, 1}});
                    }
                }
            }
        }else{
            for(auto v:g[u.s.f]){
                if(used[v.f]&&check(u.s.f, v.f, u.s.s, v.s)&&pth[v.f][u.s.s]>u.f){
                    pth[v.f][u.s.s]=u.f;
                    st1.insert({u.f, {v.f, u.s.s}});
                }else if(pth[v.f][3]>u.f+l[v.s]){
                    pth[v.f][3]=u.f+l[v.s];
                    st1.insert({u.f+l[v.s], {v.f, 3}});
                }
            }
        }
    }
    cout << min({pth[v1][0],pth[v1][1],pth[v1][2],pth[v1][3]});
}
int main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    int t=1;
    //cin >> t;
    while(t--){
        solve();
        cout << "\n";
    }
    return 0;
}

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