Submission #1167697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167697		afvrevebva	Commuter Pass (JOI18_commuter_pass)	C++20	24 / 100	2095 ms	17536 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;
    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;
    }
    ll res=M*C;
    for(int i=1;i<=n;i++){
        if(!b[i]){
            continue;
        }
        queue<int>q;
        q.push(i);
        vector<ll> d(n+1,C*M);
        d[i]=0;
        while(!q.empty()){
            int j=q.front();
            q.pop();
            if(!b[j]){
                continue;
            }
            if(d[j]+ds[i]+dt[j]==tot||d[j]+ds[j]+dt[i]==tot){
                res=min({res,du[i]+dv[j],du[j]+dv[i]});
            }
            for(pair<int,ll> p:adj[j]){
                ll k,c;
                tie(k,c)=p;
                if(d[k]>d[j]+c){
                    d[k]=d[j]+c;
                    q.push(k);
                }
            }

        }
    }
    cout<<min(res,du[v]);
}

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