Submission #233225

#	Time	Username	Problem	Language	Result	Execution time	Memory
233225		LittleFlowers__	Commuter Pass (JOI18_commuter_pass)	C++14	55 / 100	451 ms	24052 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;

    if(n<=300){
        vector<vector<int>> fw(n+1,vector<int>(n+1,INF));
        forinc(i,1,n) fw[i][i]=0;
        forinc(i,1,m){
            int x=in,y=in,w=in;
            fw[x][y]=min(fw[x][y],w);
            fw[y][x]=min(fw[y][x],w);
        }
        forinc(t,1,n) forinc(i,1,n) forinc(j,1,n) fw[i][j]=min(fw[i][j],fw[i][t]+fw[t][j]);
        int ret=fw[u][v];
        forinc(i,1,n) forinc(j,1,n)
            if(fw[s][i] + fw[i][j] + fw[j][t] == fw[s][t])
                ret=min({ret,fw[u][i]+fw[j][v],fw[u][j]+fw[i][v]});
        return cout<<ret,0;
    }

    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);

    if(s==u){
        int ret=fu[v];
        forinc(i,1,n)
            if(fs[i] + ft[i] == fs[t])
                ret=min(ret,fv[i]);
        return cout<<ret,0;
    }

    int path=0;
    forinc(i,1,n)
        if(fs[i] + ft[i] == fs[t])
            path++;

    if(path == len[t] + 1){
        int ret=fu[v];
        int pf=INF, sf=INF;
        forinc(i,1,n)
            if(fs[i] + ft[i] == fs[t])
                pf=min(pf,fu[i]), sf=min(sf,fv[i]);
        return cout<<min(ret,pf+sf),0;
    }

}

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: 0 / 45