Submission #788699

#	Time	Username	Problem	Language	Result	Execution time	Memory
788699		alecurse	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	321 ms	23852 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>
#define mp make_pair
#define ll long long int
using namespace std;
ll N,M,S,T,U,V;
vector<vector<pair<ll,ll> > > adj;
vector<ll> distS;
vector<ll> distU;
vector<ll> distV;
void dijkstra(ll from, vector<ll> &dist) {
    dist[from]=0;
    vector<bool> vis(N+1);
    priority_queue<pair<ll,ll>, vector<pair<ll,ll> >, greater<pair<ll,ll> > > q;
    q.push(mp(0,from));
    while(!q.empty()) {
        ll a=q.top().second;
        q.pop();
        if(vis[a]) continue;
        vis[a]=true;
        for(auto el : adj[a]) {
            ll b=el.first, w=el.second;
            if(dist[b]>dist[a]+w) {
                dist[b]=dist[a]+w;
                q.push(mp(dist[b],b));
            }
        }
    }
}
ll res;
vector<bool> visth;
vector<ll> distth;
void calc(ll x) {
    
    if(visth[x]) return;
    // cout<<x<<"\n";
    visth[x]=true;
    distth[x]=distU[x];
    for(auto el:adj[x]) {
        ll b=el.first, w=el.second;
        if(distS[b]==distS[x]-w) {
            calc(b);
            distth[x]=min(distth[x],distth[b]);
        } else {
            // calc(b);
            // distth[x]=min(distth[x],distth[b]+w);
        }
    }
    // cout<<x<<" "<<distth[x]+distV[x]<<"\n";
    res=min(res,distth[x]+distV[x]);
}
void calc2(ll x) {
    
    if(visth[x]) return;
    // cout<<x<<"\n";
    visth[x]=true;
    distth[x]=distV[x];
    for(auto el:adj[x]) {
        ll b=el.first, w=el.second;
        if(distS[b]==distS[x]-w) {
            calc2(b);
            distth[x]=min(distth[x],distth[b]);
        } else {
            // calc(b);
            // distth[x]=min(distth[x],distth[b]+w);
        }
    }
    // cout<<x<<" "<<distth[x]+distV[x]<<"\n";
    res=min(res,distth[x]+distU[x]);
}

int main() {
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    cin>>N>>M>>S>>T>>U>>V;
    adj.resize(N+1);
    for(ll i=0;i<M;i++) {
        ll a,b,c;
        cin>>a>>b>>c;
        adj[a].push_back(mp(b,c));
        adj[b].push_back(mp(a,c));
    }
    distS.assign(N+1,LLONG_MAX);
    dijkstra(S,distS);
    distU.assign(N+1,LLONG_MAX);
    dijkstra(U,distU);
    distV.assign(N+1,LLONG_MAX);
    dijkstra(V,distV);
    res=distU[V];

    visth.resize(N+1);
    distth.resize(N+1);
    calc(T);
    visth.clear();
    distth.clear();
    visth.resize(N+1);
    distth.resize(N+1);
    calc2(T);
    cout<<res;
}

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