Submission #341294

#	Time	Username	Problem	Language	Result	Execution time	Memory
341294		bigDuck	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	906 ms	32092 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll

int n, m, S, T, U, V;


int Ds[100010], Du[100010], Dt[100010], Dv[100010];
bool v[100010];

vector<pii> g[100010];
pair<int ,pii> e[200010];


vector<pii> g2[100010];


void dijkstra(int s, vector<pii> g[], int D[], bool v[]){
    multiset<pii> ms;
    ms.insert({0, s});
    D[s]=0;

    while(!ms.empty()){
        pii pr=(*ms.begin()); ms.erase(ms.begin());
        int node=pr.sc, d=pr.ft;
        v[node]=true;
        for(pii pr:g[node]){
            int u=pr.ft, c=pr.sc;
            if(!v[u]){
                auto it=ms.find({D[u], u});
                if(it==ms.end()){
                    D[u]=d+c;
                    ms.insert({D[u], u});
                }
                else{
                    if((d+c)<D[u]){
                        D[u]=d+c;
                        ms.erase(it);
                        ms.insert({D[u], u});
                    }
                }
            }
        }
    }
for(int i=1; i<=n;i++){
    v[i]=false;
}

}


void build_g2(){

for(int i=1; i<=m; i++){
    int u=e[i].sc.ft, v=e[i].sc.sc, c=e[i].ft;
    if( (Ds[u]+c+Dt[v])==Ds[T]  ){
        g2[u].pb({v, c});
    }
    if( (Ds[v]+c+Dt[u])==Ds[T] ){
        g2[v].pb({u, c});
    }
}

}

int res=1e18;
int mnu[100010], mnv[100010];




int dfsu(int s){

    int dv=Dv[s];
    v[s]=true;
    for(pii pr:g2[s]){
        int u=pr.ft;
        dv=min(dv, Dv[u]);
        if(!v[u]){
        dv=min(dfsu(u), dv);}
        dv=min(dv, mnv[u]);
    }
    res=min(res, Du[s]+dv);
    mnv[s]=dv;
    return dv;
}

int dfsv(int s){

    int du=Du[s];
    v[s]=true;
    for(pii pr:g2[s]){
        int u=pr.ft;
        du=min(du, Du[u]);
        if(!v[u]){
        du=min(dfsv(u), du);}
        du=min(du, mnu[u]);
    }
    res=min(res, du+Dv[s]);
    mnu[s]=du;
    return du;
}



int32_t main(){
INIT
cin>>n>>m;
cin>>S>>T;
cin>>U>>V;

for(int i=1; i<=m; i++){
    int u, v, c;
    cin>>u>>v>>c;
    g[u].pb({v, c});
    g[v].pb({u, c});
    e[i]={c, {u, v}};
}

dijkstra(S, g, Ds, v);
dijkstra(T, g, Dt, v);
dijkstra(U, g, Du, v);
dijkstra(V, g, Dv, v);
build_g2();



dfsu(S);
for(int i=1; i<=n; i++){
    v[i]=false;
}

dfsv(S);







cout<<min(res, Du[V]);

return 0;
}

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