Submission #782168

#	Time	Username	Problem	Language	Result	Execution time	Memory
782168		8pete8	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	289 ms	262144 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pb push_back
#define p push
#define pii pair<int,int>
#define ppii pair<int,pii>
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#define set(x) memset(x,-1,sizeof(x));
const int mxn=1e5+1,mod=1e9+7;
#define int long long
int n,m,s,t,u,v,sz,cost,ans=-1;
vector<int> pa[mxn+10];
vector<pii>adj[mxn+10];
vector<bitset<mxn+10>>path;
bitset<mxn+10>vis,vis2[mxn+10];
void dijk(){
    vector<int>dist(n+1,-1);
    priority_queue<pii,vector<pii>,greater<pii>>pq;
    dist[s]=0;
    pq.p({0,s});
    while(!pq.empty()){
        int cur=pq.top().s;
        pq.pop();
        if(vis[cur])continue;
        if(cur==t)break;
        vis[cur]=true;
        for(auto i:adj[cur]){
            if(dist[i.f]==-1||dist[i.f]>dist[cur]+i.s){
                dist[i.f]=dist[cur]+i.s;
                pa[i.f].clear();
                pa[i.f].pb(cur);
                pq.p({dist[i.f],i.f});
            }
            else if(dist[i.f]==dist[cur]+i.s)pa[i.f].pb(cur);
        }
    }
}
void solve(){
    vector<vector<int>>dp(n+1,vector<int>(sz+1,-1));
    priority_queue<ppii,vector<ppii>,greater<ppii>>pq;
    for(int i=0;i<path.size();i++)pq.p({0,{u,i}}),dp[u][i]=0;
    while(!pq.empty()){
        int cur=pq.top().s.f,comp=pq.top().s.s;
        pq.pop();
        if(cur==v){
            if(ans==-1)ans=dp[cur][comp];
            else ans=min(ans,dp[cur][comp]);
            continue;
        }
        if(vis2[cur][comp])continue;
        vis2[cur][comp]=true;
        for(auto i:adj[cur]){
            cost=i.s;
            if(path[comp][cur]&&path[comp][i.f]){
                cost=0;
            }
            if(dp[i.f][comp]==-1||dp[i.f][comp]>dp[cur][comp]+cost)dp[i.f][comp]=dp[cur][comp]+cost,pq.p({dp[i.f][comp],{i.f,comp}});
        }
    }
}
int32_t main(){
    fastio
    cin>>n>>m>>s>>t>>u>>v;
    while(m--){
        int a,b,c;cin>>a>>b>>c;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
    }
   
    queue<pair<int,bitset<mxn+10>>>q;
    dijk();
    vis.reset();
    q.p({t,vis});
    while(!q.empty()){
        q.front().s[q.front().f]=true;
        for(auto i:pa[q.front().f])q.p({i,q.front().s});
        if(q.front().f==s)path.pb(q.front().s);
        q.pop();
    }
    solve();
    cout<<ans;
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:44:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::bitset<100011> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=0;i<path.size();i++)pq.p({0,{u,i}}),dp[u][i]=0;
      |                 ~^~~~~~~~~~~~

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