Submission #439662

#	Time	Username	Problem	Language	Result	Execution time	Memory
439662		Deepesson	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	646 ms	56444 KiB

commuter_pass

#include <bits/stdc++.h>
#define MAX 101000
bool rota[MAX];
typedef std::pair<long long,long long> pii;
typedef std::pair<long long,pii> pip;
std::vector<long long> veio[MAX];
std::map<long long,bool> mapa[MAX];
std::vector<long long> levou[MAX];

std::vector<pii> con[MAX];
bool dp_check[MAX],dp_res[MAX];
long long S,T,U,V;
bool dp(int x){
    if(dp_check[x])return dp_res[x];
    dp_check[x]=true;
    for(auto&z:veio[x]){
        if(dp(z)){
            dp_res[x]=rota[x]=true;
        }
    }
    return dp_res[x];
}
long long valextra[MAX],pesmin[MAX];
long long inf =1000000000000000000LL;
long long dpb[MAX],dpu[MAX],cup[MAX],cbai[MAX];
long long dpbai(int x) {
    if(cbai[x])return dpb[x];
    dpb[x]=inf;
    cbai[x]=true;
    long long min = pesmin[x];
    for(auto&z:veio[x]) {
        if(rota[z])
        min=std::min(min,dpbai(z));
    }
    return dpb[x]=min;
}
long long dpup(int x) {
    if(cup[x])return dpu[x];
    dpu[x]=inf;
    cup[x]=true;
    long long min = pesmin[x];
    for(auto&z:levou[x]) {
        if(rota[z]&&mapa[x].find(z)==mapa[x].end())
        min=std::min(min,dpup(z));
    }
    return dpu[x]=min;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int N,M;
    std::cin>>N>>M;
    std::cin>>S>>T>>U>>V;--S;--T;--U;--V;
    for(int i=0;i!=M;++i){
        long long a,b,c;
        std::cin>>a>>b>>c;--a;--b;
        con[a].push_back({b,c});
        con[b].push_back({a,c});
    }
    ///Rotas
    {
        bool visitou[N]={};
        long long custos[N]={};for(auto&x:custos)x=inf;
        std::priority_queue<pip,std::vector<pip>,std::greater<pip>> queue;
        queue.push({0LL,{S,S}});
        while(queue.size()){
            auto _ = queue.top();
            queue.pop();
            auto custo = _.first;
            auto atual = _.second.first;
            auto prev = _.second.second;
            if(custos[atual]>=custo){
                veio[atual].push_back(prev);
                mapa[atual][prev]=true;
                levou[prev].push_back(atual);
            }
            if(visitou[atual])continue;
            visitou[atual]=true;
            custos[atual]=custo;
            for(auto&x:con[atual]){
                queue.push({custo+x.second,{x.first,atual}});
            }
        }
        dp_res[S]=dp_check[S]=rota[S]=true;
        dp(T);
    }
    ///Peso Minimo para V
    {
       bool visitou[N]={};
       std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
       queue.push({0LL,V});
       while(queue.size()){
            auto _ = queue.top();
            queue.pop();
            auto custo = _.first;
            auto atual = _.second;
            if(visitou[atual])continue;
            visitou[atual]=true;
            pesmin[atual]=custo;
            for(auto&x:con[atual]){
                queue.push({custo+x.second,x.first});
            }
        }
    }
    ///Caminhos Minimos (2 DPs)
    {
        for(int i=0;i!=N;++i){
            if(rota[i]){
                valextra[i]=std::min(dpup(i),dpbai(i));
            }
        }
    }
    bool visitou[N]={};
    std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
    queue.push({0LL,U});
    while(queue.size()){
        auto _ = queue.top();
        queue.pop();
        auto custo = _.first;
        auto atual = _.second;
        if(visitou[atual])continue;
        visitou[atual]=true;
        if(atual==V){
            std::cout<<custo<<"\n";
            return 0;
        }
        if(rota[atual]){
            queue.push({custo+valextra[atual],V});
        }
        for(auto&x:con[atual]){
            queue.push({custo+x.second,x.first});
        }
    }
    assert(0);
    std::cout<<"-1\n";
}

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