Submission #1204948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204948		Younis_Dwai	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	208 ms	35556 KiB

commuter_pass

//#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
//#define endl "\n"
#define F first
#define S second
#define pb push_back
#define pf push_front
#define popf pop_frot
#define popb pop_back
#define int long long
#define in insert
//#define mid (l+r)/2
//register int cnt
using namespace std;
const int N=1e5+5;
int n,m,S,T,U,V,dp[N][4][2],dis[5][N],vis[N],k=0;
vector<pair<int,int>> adj[N];
vector<int> E[N][2];
void calc(int G){
     ++k;
     for(int i=1;i<=n;i++) vis[i]=0;
     for(int i=1;i<=n;i++) dis[k][i]=1e17;
     dis[k][G]=0;
     priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
     q.push({0,G});
     while(!q.empty()){
           int node=q.top().S,d=q.top().F;
           q.pop();
           if(vis[node]) continue ;
           vis[node]=1;
           for(auto u : adj[node]){
               if(dis[k][u.F]>u.S+d){
                  dis[k][u.F]=u.S+d;
                  q.push({dis[k][u.F],u.F});
               }
           }
     }
     return ;
}
int rec(int node , int type , int t){
    if(dp[node][type][t]!=-1) return dp[node][type][t];
    int ret=dis[type][node];
    for(auto u : E[node][t]){
        ret=min(ret,rec(u,type,t));
    }
    return dp[node][type][t]=ret;
}
int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(nullptr);
    memset(dp,-1,sizeof dp);
    cin>>n>>m;
    cin>>S>>T;
    cin>>U>>V;
    for(int i=1;i<=m;i++){
        int x,y,z;cin>>x>>y>>z;
        adj[x].pb({y,z});
        adj[y].pb({x,z});
    }
    calc(S);
    calc(U);
    calc(V);
    calc(T);
    memset(vis,0,sizeof vis);
    queue<int> q;
    q.push(T);
    while(!q.empty()){
           int node=q.front();
           q.pop();
           vis[node]=1;
           for(auto u : adj[node]){
               if(dis[1][u.F]+u.S==dis[1][node] && vis[u.F]==0){
                  E[node][0].pb(u.F);
                  E[u.F][1].pb(node);
                  vis[u.F]=1;
                  q.push(u.F);
               }
           }
    }
    int ret=dis[2][V];
    for(int i=1;i<=n;i++){
        if(vis[i]){
           ret=min({ret,dis[2][i]+rec(i,3,0),dis[2][i]+rec(i,3,1)});
       }
    }
    cout<<ret;
    return 0;
}

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