Submission #1167906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167906		kla	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	200 ms	15896 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
vector<pair<int, int>>M[100001];
bool biju [100001]={};
long long U[100001]={};
long long V[100001]={};
long long bals[100001]={};
long long kopy[100001]={};
pair<long long, long long> pr[100001]={};
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>>pq={};
long long nxt(){
    long long n;
    cin>>n;
    return n;
}
void DjikstrasimU(int sak){
    U[sak]=0, pq.push(make_pair(0, sak));
    while(pq.size()!=0){
        int v=pq.top().second;
        long long att=pq.top().first;
        pq.pop();
        if(biju[v]==0){
            biju[v]=1;
            for(auto c: M[v]){
                if(att+c.second<U[c.first]){
                        U[c.first]=att+c.second, pq.push(make_pair(U[c.first], c.first));
                }
            }
        }
    }
}
void DjikstrasimV(int sak){
    V[sak]=0, pq.push(make_pair(0, sak));
    while(pq.size()!=0){
        int v=pq.top().second;
        long long att=pq.top().first;
        pq.pop();
        if(biju[v]==0){
            biju[v]=1;
            for(auto c: M[v]){
                if(att+c.second<V[c.first]){
                        V[c.first]=att+c.second, pq.push(make_pair(V[c.first], c.first));
                }
            }
        }
    }
}
long long Djikstra(int sak, int ender, long long iss){
    bals[sak]=0;
    pr[sak]={V[sak], U[sak]};
    pq.push(make_pair(0, sak));
    while(pq.top().second!=ender){
        int v=pq.top().second;
        //cout<<v<<' '<<pr[v].first<<' '<<pr[v].second<<'\n';
        long long att=pq.top().first, vak=pr[v].first, uak=pr[v].second;
        pq.pop();
        if(biju[v]==0){
            biju[v]=1;
            for(auto c: M[v]){
                if(c.second+att<=bals[c.first]&&kopy[c.first]>=min(vak, V[c.first])+min(uak, U[c.first]))
                    bals[c.first]=c.second+att, kopy[c.first]=min(vak, V[c.first])+min(uak, U[c.first]),
                    pr[c.first].first=min(vak, V[c.first]), pr[c.first].second=min(uak, U[c.first]), pq.push(make_pair(bals[c.first], c.first));
            }
        }
    }
    return min(iss, kopy[ender]);
}
int main()
{
    long long  n, m, s, t, u, v, sk1, sk2, sv;
    cin>>n>>m>>s>>t>>u>>v;
    for(int i=0; i<m; i++){
        sk1=nxt(), sk2=nxt(), sv=nxt();
        M[sk1].push_back({sk2, sv});
        M[sk2].push_back({sk1, sv});
    }
    for(int i=1; i<=n; i++)U[i]=LONG_LONG_MAX, V[i]=LONG_LONG_MAX,
        bals[i]=LONG_LONG_MAX, kopy[i]=LONG_LONG_MAX, pr[i]={LONG_LONG_MAX, LONG_LONG_MAX};
    DjikstrasimU(u);
    fill(biju, biju+n+1, 0);
    DjikstrasimV(v);
    fill(biju, biju+n+1, 0);
    cout<<Djikstra(s, t, U[v])<<endl;
    return 0;
}

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