Submission #1167763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167763		afvrevebva	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	2093 ms	327680 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll C=1e9;
const ll M=2e5;

vector<vector<pair<int,ll>>> adj;

void f(vector<ll> &v,int x){
    v[x]=0;
    auto comp=[&v](int i,int j){return v[i]>v[j];};
    priority_queue<int,vector<int>,decltype(comp)>pq{comp};
    pq.push(x);
    while(!pq.empty()){
        int i=pq.top();
        pq.pop();
        for(pair<int,ll> p:adj[i]){
            ll j,c;
            tie(j,c)=p;
            if(v[j]>v[i]+c){
                v[j]=v[i]+c;
                pq.push(j);
            }
        }
    }
}

void f1(vector<ll> &v,int x){
    v[x]=0;
    queue<int>q;
    q.push(x);
    while(!q.empty()){
        int i=q.front();
        q.pop();
        for(pair<int,ll> p:adj[i]){
            ll j,c;
            tie(j,c)=p;
            if(v[j]>v[i]+c){
                v[j]=v[i]+c;
                q.push(j);
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    ll n,m,s,t,u,v;
    cin>>n>>m>>s>>t>>u>>v;
    adj=vector<vector<pair<int,ll>>>(n+1);
    for(int i=0;i<m;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    vector<ll> du(n+1,C*M);
    vector<ll> dv(n+1,C*M);
    vector<ll> dt(n+1,C*M);
    vector<ll> ds(n+1,C*M);
    f(du,u);
    f(dv,v);
    f(ds,s);
    f(dt,t);
    ll tot=C*M;
    for(int i=1;i<=n;i++){
        tot=min(tot,ds[i]+dt[i]);
    }
    vector<bool> b(n+1);
    for(int i=1;i<=n;i++){
        b[i]=ds[i]+dt[i]==tot;
    }
    vector<pair<ll,ll>> dp(n+1,{C*M,C*M});
    dp[s]={du[s],dv[s]};
    auto comp=[&ds](int i,int j){return ds[i]>ds[j];};
    priority_queue<ll,vector<ll>,decltype(comp)>pq{comp};
    pq.push(s);
    ll res=M*C;
    while(!pq.empty()){
        int i=pq.top();
        pq.pop();
        for(pair<int,ll> p:adj[i]){
            int j=p.first;
            if(ds[j]>ds[i]&&b[j]){
                pq.push(j);
                dp[j].first=min({dp[i].first,dp[j].first,du[j]});
                dp[j].second=min({dp[i].second,dp[j].second,dv[j]});
                res=min({res,dp[j].first+dv[j],dp[j].second+du[j]});
            }
        }
    }
    cout<<min(res,du[v]);
}

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