Submission #1265439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265439		hitsuuj	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	251 ms	20928 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define lc 2*pos
#define rc 2*pos+1
#define pii pair<int,int>
#define fi first
#define se second
//CEK ENDL DAN INT LL
#define endl '\n'
#define inf 1e18
#define ti tuple<int,int,int>
#define meekucaon ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int mod=1e9+7;
int sf(int a){return (a%mod+mod)%mod;}
int kal(int a,int b){return (sf(a)*sf(b))%mod;}
int tam(int a,int b){return (sf(a)+sf(b))%mod;}
int kur(int a,int b){return (sf(a)+mod-sf(b))%mod;}
int inv(int a){
    if(a<=1) return 1;
    return mod-(int)(mod/a)*inv(mod%a)%mod;
}
int bag(int a,int b){return kal(sf(a),inv(b));}
const int lim=100000;
int dis[5][lim+10];
vector<pii>g[lim+10];
int n,m,s,t,a,b;
int nodso(int u,int v,int w){
    if(dis[1][u]+dis[0][v]+w==dis[0][t]) return 1;
    if(dis[0][u]+dis[1][v]+w==dis[0][t]) return 1;
    return 0;
}
void dji(int ta,int st){
    priority_queue<pii,vector<pii>,greater<pii>>q;
    q.push({0,st});
    dis[ta][st]=0;
    while(q.size()){
        auto [d,u]=q.top();
        q.pop();
        if(dis[ta][u]<d) continue; 
        for(auto [v,w]:g[u]){
            if(dis[ta][u]+w>=dis[ta][v]) continue;
            dis[ta][v]=dis[ta][u]+w;
            q.push({dis[ta][v],v});
        }
    }
}
int vis[lim+10];
int par[lim+10];
signed main(){
    meekucaon
    cin>>n>>m>>s>>t>>a>>b;
    int dp[2][n+10];
    for(int i=1;i<=n;i++){
        dp[0][i]=inf;
        dp[1][i]=inf;
        for(int j=0;j<4;j++){
            dis[j][i]=inf;
        }
    }
    for(int i=1;i<=m;i++){
        int u,v,w;cin>>u>>v>>w;
        g[u].pb({v,w});
        g[v].pb({u,w});
    }
    dji(0,s);dji(1,t);dji(2,a);dji(3,b);
    queue<int>q;
    q.push(s);
    while(q.size()){
        int u=q.front();
        q.pop();
        vis[u]=1;
        for(auto [v,w]:g[u]){
            if(dis[0][u]+w+dis[1][v]!=dis[0][t]) continue;
            if(!vis[v])q.push(v);
            par[v]++;
        }
    }
    for(int i=1;i<=n;i++)vis[i]=0;
    q.push(s);
    int ans=dis[3][a];
    while(q.size()){
        int u=q.front();
        q.pop();
        vis[u]=1;
        // cout<<u<<' '<<dis[2][u]<<' '<<dis[3][u]<<endl;
        dp[0][u]=min(dp[0][u],dis[2][u]);
        dp[1][u]=min(dp[1][u],dis[3][u]);
        ans=min(ans,dp[0][u]+dp[1][u]);
        for(auto [v,w]:g[u]){
            if(dis[0][u]+w+dis[1][v]==dis[0][t]){
                dp[0][v]=min(dp[0][u],dp[0][v]);
                dp[1][v]=min(dp[1][u],dp[1][v]);
                // cout<<u<<" "<<v<<" "<<par[v]<<endl;
                par[v]--;
                if(!par[v] && !vis[v])q.push(v);
            }
        }
    }
    cout<<ans;
    
}
// 1. pasti dp 


// obs 
// 1. kalau masuk dalam shortest path bebas masuk keluar mana aja 
// 2. save smallest dari suatu node ke s,t,a,b
// // subsoal 
// // (1 & 2)
// // kalau masi masuk shortest path = 0
// // (3)
// // N<=300 
// // tiap shortest route x all 

// subtask 3
// n*n*n cek apakah ij dalam satu lane if yes then take min 


// how to make it in m/n 

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