Submission #945496

#	Time	Username	Problem	Language	Result	Execution time	Memory
945496		irmuun	Commuter Pass (JOI18_commuter_pass)	C++17	16 / 100	342 ms	24068 KiB

commuter_pass

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,m;
    cin>>n>>m;
    ll S,T,U,V;
    cin>>S>>T>>U>>V;
    vector<pair<ll,ll>>adj[n+5];
    for(ll i=1;i<=m;i++){
        ll u,v,w;
        cin>>u>>v>>w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    vector<vector<ll>>dist(4,vector<ll>(n+5,1e18));
    dist[0][S]=0;
    dist[1][T]=0;
    dist[2][U]=0;
    dist[3][V]=0;
    set<pair<ll,ll>>st;
    st.insert({0,S});
    while(!st.empty()){
        auto [D,i]=*st.begin();
        st.erase(st.begin());
        if(dist[0][i]!=D) continue;
        for(auto [j,c]:adj[i]){
            if(dist[0][j]>dist[0][i]+c){
                dist[0][j]=dist[0][i]+c;
                st.insert({dist[0][j],j});
            }
        }
    }
    st.insert({0,T});
    while(!st.empty()){
        auto [D,i]=*st.begin();
        st.erase(st.begin());
        if(dist[1][i]!=D) continue;
        for(auto [j,c]:adj[i]){
            if(dist[1][j]>dist[1][i]+c){
                dist[1][j]=dist[1][i]+c;
                st.insert({dist[1][j],j});
            }
        }
    }
    st.insert({0,U});
    while(!st.empty()){
        auto [D,i]=*st.begin();
        st.erase(st.begin());
        if(dist[2][i]!=D) continue;
        for(auto [j,c]:adj[i]){
            if(dist[2][j]>dist[2][i]+c){
                dist[2][j]=dist[2][i]+c;
                st.insert({dist[2][j],j});
            }
        }
    }
    st.insert({0,V});
    while(!st.empty()){
        auto [D,i]=*st.begin();
        st.erase(st.begin());
        if(dist[3][i]!=D) continue;
        for(auto [j,c]:adj[i]){
            if(dist[3][j]>dist[3][i]+c){
                dist[3][j]=dist[3][i]+c;
                st.insert({dist[3][j],j});
            }
        }
    }
    // S T U V
    if(S==U){
        ll ans=1e18;
        for(ll i=1;i<=n;i++){
            if(dist[0][i]+dist[1][i]==dist[0][T]){
                ans=min(ans,dist[3][i]);
            }
        }
        cout<<ans;
        return 0;
    }
    cout<<0;
}

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