Submission #1167607

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

commuter_pass

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

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

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;
    vector<vector<pair<int,ll>>> adj(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> cu(n+1,C*M);
    cu[u]=0;
    queue<int> q;
    q.push(u);
    while(!q.empty()){
        int i=q.front();
        q.pop();
        for(pair<int,int> p:adj[i]){
            ll j,c;
            tie(j,c)=p;
            if(cu[j]>cu[i]+c){
                cu[j]=cu[i]+c;
                q.push(j);
            }
        }
    }
    vector<ll> cv(n+1,C*M);
    cv[v]=0;
    q.push(v);
    while(!q.empty()){
        int i=q.front();
        q.pop();
        for(pair<int,int> p:adj[i]){
            ll j,c;
            tie(j,c)=p;
            if(cv[j]>cv[i]+c){
                cv[j]=cv[i]+c;
                q.push(j);
            }
        }
    }
    vector<vector<ll>> cs(n+1,vector<ll>(3,C*M));
    cs[s][0]=0;
    cs[s][1]=cu[s];
    cs[s][2]=cv[s];
    q.push(s);
    while(!q.empty()){
        int i=q.front();
        q.pop();
        for(pair<int,int> p:adj[i]){
            ll j,c;
            tie(j,c)=p;
            if(cs[j][0]>=cs[i][0]+c){
                cs[j][0]=cs[i][0]+c;
                ll mn1=min(cs[i][1],cu[j]);
                ll mn2=min(cs[i][2],cv[j]);
                if(cs[j][1]+cs[j][1]>mn1+mn2){
                    cs[j][1]=mn1;
                    cs[j][2]=mn2;
                }
                q.push(j);
            }
        }
    }
    cout<<min(cs[t][1]+cs[t][2],cu[v])<<"\n";
}

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