Submission #540227

#	Time	Username	Problem	Language	Result	Execution time	Memory
540227		krit3379	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	501 ms	28336 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define N 100005

struct A{
    long long a,w,p;
    bool operator<(const A& o)const{
        return w>o.w;
    }
};

long long ans;
vector<vector<long long>> dis(2,vector<long long>(N,1e18));
vector<A> g[N];
priority_queue<A> q;
bitset<N> vis;

void dijk(int idx,int s){
    q.push({s,0});
    dis[idx][s]=0;
    while(!q.empty()){
        auto [a,w,p]=q.top();
        q.pop();
        if(w>dis[idx][a])continue;
        for(auto x:g[a]){
            if(w+x.w<dis[idx][x.a])q.push({x.a,w+x.w}),dis[idx][x.a]=w+x.w;
        }
    }
}

void dijk2(int s,int e){
    vector<long long> diss(N,1e18);
    vector<vector<long long>> dp(2,vector<long long>(N,1e18));
    vis=0;
    q.push({s,0,0});
    while(!q.empty()){
        auto [a,w,p]=q.top();
        q.pop();
        if(!vis[a]){
            vis[a]=true;
            diss[a]=w;
            dp[0][a]=min(dis[0][a],dp[0][p]);
            dp[1][a]=min(dis[1][a],dp[1][p]);
            for(auto x:g[a])q.push({x.a,w+x.w,a});
        }
        else if(w==diss[a]&&min(dis[0][a],dp[0][p])+min(dis[1][a],dp[1][p])<dp[0][a]+dp[1][a])dp[0][a]=min(dis[0][a],dp[0][p]),dp[1][a]=min(dis[1][a],dp[1][p]);
    }
    ans=min(ans,dp[0][e]+dp[1][e]);
}

int main(){
    int n,m,s,t,u,v,i,a,b;
    long long w,mi;
    scanf("%d %d %d %d %d %d",&n,&m,&s,&t,&u,&v);
    for(i=1;i<=m;i++){
        scanf("%d %d %lld",&a,&b,&w);
        g[a].push_back({b,w});
        g[b].push_back({a,w});
    }
    dijk(0,u);
    dijk(1,v);
    ans=dis[0][v];
    dijk2(s,t);
    dijk2(t,s);
    printf("%lld",ans);
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:53:17: warning: unused variable 'mi' [-Wunused-variable]
   53 |     long long w,mi;
      |                 ^~
commuter_pass.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d %d %d %d %d %d",&n,&m,&s,&t,&u,&v);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%d %d %lld",&a,&b,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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