Submission #1158764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158764		the_ZHER	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	2094 ms	35084 KiB

commuter_pass

#include <bits/stdc++.h>
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
const int inf=1e17;
const int N=1e5+5;
const int N1=1e5+5;
const int N2=5e6+6;
const int mod=1e9+7;
const int k1=447;
struct edge{
    int d,in;
};
struct edge1{
    int x,y,c;
};
vector<pair<int,int> >v1[N];
vector<pair<int,int> >v3[N];
vector<edge1>v2;
int dp[6][N];
void djk(int a,int in){
    dp[in][a]=0;
    set<pair<int,int> >st;
    st.insert({a,0ll});
    while(st.size()>0){
        pair<int,int>b=*st.begin();
        st.erase(st.begin());
        for(int i=0;i<v1[b.first].size();i++){
            pair<int,int> x=v1[b.first][i];
            if(dp[in][x.first]>dp[in][b.first]+x.second){
                st.erase({x.first,dp[in][x.first]});
                dp[in][x.first]=dp[in][b.first]+x.second;
                st.insert({x.first,dp[in][x.first]});
            }
        }
    }
}
void djk1(int a,int in){
    dp[in][a]=0;
    set<pair<int,int> >st;
    st.insert({a,0ll});
    while(st.size()>0){
        pair<int,int>b=*st.begin();
        st.erase(st.begin());
        for(int i=0;i<v3[b.first].size();i++){
            pair<int,int> x=v3[b.first][i];
            if(dp[in][x.first]>dp[in][b.first]+x.second){
                st.erase({x.first,dp[in][x.first]});
                dp[in][x.first]=dp[in][b.first]+x.second;
                st.insert({x.first,dp[in][x.first]});
            }
        }
    }
}
signed main(){
boost;
    int n,m,s,t,u,v;
    cin>>n>>m>>s>>t>>u>>v;
    for(int i=1;i<=m;i++){
        int x,y,c;
        cin>>x>>y>>c;
        v2.push_back({x,y,c});
        v1[x].push_back({y,c});
        v1[y].push_back({x,c});
    }
    for(int i=0;i<=3;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=inf;
        }
    }
    djk(s,0);
    djk(t,1);
    int cnt=dp[0][t];
    for(int i=0;i<m;i++){
        edge1 x=v2[i];
        if(dp[0][x.x]+dp[1][x.y]+x.c==cnt){
            v3[x.x].push_back({x.y,0ll});
        }else{
            v3[x.x].push_back({x.y,x.c});
        }
        if(dp[1][x.x]+dp[0][x.y]+x.c==cnt){
            v3[x.y].push_back({x.x,0ll});
        }else{
            v3[x.y].push_back({x.x,x.c});
        }
    }
    djk1(u,2);
    cout<<dp[2][v];
}  

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