Submission #233230

#	Time	Username	Problem	Language	Result	Execution time	Memory
233230		LittleFlowers__	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	496 ms	23872 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define gg exit(0);

const int N=100010,
          INF=1e15;

int n,m,s,t,u,v;
int len[N];
vector<ii> ad[N];

void dij(int fw,vector<int>&f){
    fill(all(f),INF);
    priority_queue<ii,vector<ii>,greater<ii>> q;
    q.push({0,fw}); f[fw]=len[fw]=0;
    while(q.size()){
        int w,u; tie(w,u)=q.top(); q.pop();
        forv(v,ad[u]){
            if(f[v.fi]>w+v.se){
                f[v.fi]=w+v.se;
                len[v.fi]=len[u]+1;
                q.push({w+v.se,v.fi});
            }
        }
    }
}

main(){
    #define task "pass"
    //freopen(task".inp","r",stdin);
    //freopen(task".out","w",stdout);

    n=in,m=in,s=in,t=in,u=in,v=in;

    forinc(i,1,m){
        int x=in,y=in,w=in;
        ad[x].push_back({y,w});
        ad[y].push_back({x,w});
    }

    vector<int> fs(n+1),ft(n+1),fu(n+1),fv(n+1);

    dij(t,ft);
    dij(u,fu);
    dij(v,fv);
    dij(s,fs);


    int ret=fu[v];
    forinc(w,0,1){
        vector<int> f(n+1,INF), pf(n+1,INF);
        priority_queue<ii,vector<ii>,greater<ii>> q; q.push({0,s}); f[s]=0; pf[s]=fu[s];
        while(q.size()){
            int w,u; tie(w,u)=q.top(); q.pop();
            ret=min(ret,pf[u] + fv[u]);
            forv(v,ad[u]){
                if(fs[v.fi] + ft[v.fi] == fs[t]){
                    pf[v.fi]=min({pf[v.fi],fu[v.fi],pf[u]});
                    if(f[v.fi]>w+v.se){
                        f[v.fi]=w+v.se;
                        q.push({w+v.se,v.fi});
                    }
                }
            }
        }
        swap(fv,fu);
    }
    cout<<ret;
}

Compilation message (stderr)

commuter_pass.cpp:46:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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