Submission #907396

#	Time	Username	Problem	Language	Result	Execution time	Memory
907396		RedSnow389	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	383 ms	34244 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define ld long double
#define fr(i,sz) for(i=0;i<sz;i++)
#define fa(i,v) for(auto &i:v)
#define yesno cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define vvl vector<vector<ll> >       
#define vl vector<ll>  
#define pll pair<ll,ll>  
#define vpll vector<pair<ll,ll> > 
#define vvpll vector<vector<pair<ll,ll> > > 
#define mp make_pair
#define pb push_back
#define rs resize
#define cl(v) v.clear()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define inf (ll)1e18
#define f1 first
#define f2 second
#define mod (ll)(1e9+7)
ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}

int main(){
    fastio
    int t=1;
    // cin>>t;
    while(t--){
        ll n,m,s,t,u,w,i,ans1=inf,ans=inf;
        cin>>n>>m>>s>>t>>u>>w;
        vvpll v(n+1);
        vvl fromt(n+1), froms(n+1);
        while(m--){
            ll x,y,z;
            cin>>x>>y>>z;
            v[x].pb(mp(y,z));
            v[y].pb(mp(x,z));
        }
        vl distu(n+1,inf), distv(n+1,inf), dists(n+1,inf), distt(n+1,inf), newdists(n+1,inf), newdistt(n+1,inf);
        priority_queue<pll,vpll,greater<pll> > q;
        distu[u]=0;
        q.push(mp(0,u));
        while(!q.empty()){
            ll a=q.top().f2, b=q.top().f1;
            q.pop();
            if(distu[a]<b) continue;
            fa(i,v[a]) if(distu[i.f1]>b+i.f2){
                distu[i.f1]=b+i.f2;
                q.push(mp(distu[i.f1],i.f1));
            }
        }
        distv[w]=0;
        q.push(mp(0,w));
        while(!q.empty()){
            ll a=q.top().f2, b=q.top().f1;
            q.pop();
            if(distv[a]<b) continue;
            fa(i,v[a]) if(distv[i.f1]>b+i.f2){
                distv[i.f1]=b+i.f2;
                q.push(mp(distv[i.f1],i.f1));
            }
        }
        dists[s]=0;
        q.push(mp(0,s));
        vl vis(n+1,0);
        while(!q.empty()){
            ll a=q.top().f2, b=q.top().f1;
            q.pop();
            if(dists[a]<b) continue;
            fa(i,v[a]) if(dists[i.f1]>b+i.f2){
                fromt[i.f1].clear();
                fromt[i.f1].pb(a);
                dists[i.f1]=b+i.f2;
                q.push(mp(dists[i.f1],i.f1));
            }
            else if(dists[i.f1]==b+i.f2) fromt[i.f1].pb(a);
        }
        distt[t]=0;
        q.push(mp(0,t));
        while(!q.empty()){
            ll a=q.top().f2, b=q.top().f1;
            q.pop();
            if(distt[a]<b) continue;
            fa(i,v[a]) if(distt[i.f1]>b+i.f2){
                froms[i.f1].clear();
                froms[i.f1].pb(a);
                distt[i.f1]=b+i.f2;
                q.push(mp(distt[i.f1],i.f1));
            }
            else if(distt[i.f1]==b+i.f2) froms[i.f1].pb(a);
        }
        queue<ll> q1;
        ans=distu[w];
        q1.push(s);
        newdists[s]=distu[s];
        ans=min(ans,distv[s]+distu[s]);
        while(!q1.empty()){
            ll a=q1.front();
            q1.pop();
            if(vis[a]) continue;
            vis[a]=1;
            fa(i,froms[a]){
                q1.push(i);
                newdists[i]=min(newdists[a],distu[i]);
                ans=min(ans,newdists[i]+distv[i]);
            }
        }
        q1.push(t);
        newdistt[t]=distu[t];
        vis.assign(n+1,0);
        ans=min(ans,distv[t]+distu[t]);
        while(!q1.empty()){
            ll a=q1.front();
            q1.pop();
            if(vis[a]) continue;
            vis[a]=1;
            fa(i,fromt[a]){
                q1.push(i);
                newdistt[i]=min(newdistt[a],distu[i]);
                ans=min(ans,newdistt[i]+distv[i]);
            }
        }
        cout<<ans;
        // fr(i,n) cout<<distu[i+1]<<' ';
        // fr(i,n) cout<<distv[i+1]<<' ';
    }   
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:30:24: warning: unused variable 'i' [-Wunused-variable]
   30 |         ll n,m,s,t,u,w,i,ans1=inf,ans=inf;
      |                        ^
commuter_pass.cpp:30:26: warning: unused variable 'ans1' [-Wunused-variable]
   30 |         ll n,m,s,t,u,w,i,ans1=inf,ans=inf;
      |                          ^~~~

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