Submission #880568

#	Time	Username	Problem	Language	Result	Execution time	Memory
880568		codexistent	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	396 ms	27020 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(long long i = a; i <= b; i++)
#define MAXN 100005

vector<long long> sp1 (long long N, vector<vector<pair<long long, long long> > > const &E, long long r){
    priority_queue<pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long> > > pq; pq.push(make_pair(0, r));
    bool V[N] = {false};
    vector<long long> D; D.resize(N); fill(begin(D), end(D), LONG_LONG_MAX); D[r] = 0;
    while(!pq.empty()){
        long long n = pq.top().second; pq.pop();
        if(V[n]) continue;

        for(auto e : E[n]) if(D[e.first] > D[n] + e.second) {
            D[e.first] = D[n] + e.second;
            pq.push(make_pair(D[e.first], e.first));
        }
    }

    return D;
}
vector<pair<long long, long long> > sp2 (long long N, vector<vector<pair<long long, long long> > > const &E, vector<long long> const &BD, long long r){
    priority_queue<pair<pair<long long, long long>, long long>, vector<pair<pair<long long, long long>, long long> >, greater<pair<pair<long long, long long>, long long> > > pq; pq.push(make_pair(make_pair(0, BD[r]), r));
    bool V[N] = {false};
    vector<pair<long long, long long> > D; D.resize(N); fill(begin(D), end(D), make_pair(LONG_LONG_MAX, LONG_LONG_MAX)); D[r] = make_pair(0, BD[r]);
    while(!pq.empty()){
        long long n = pq.top().second; pq.pop();
        if(V[n]) continue;

        for(auto e : E[n]) if(D[e.first] > make_pair(D[n].first + e.second, min(D[n].second, BD[e.first]))) {
            D[e.first] = make_pair(D[n].first + e.second, min(D[n].second, BD[e.first]));
            pq.push(make_pair(D[e.first], e.first));
        }
    }

    return D;
}

int main(){
    long long N, M, S, T, U, V;
    cin >> N >> M;
    cin >> S >> T >> U >> V; S--, T--, U--, V--;
    vector<vector<pair<long long, long long> > > E;
    E.resize(N);
    FOR(i, 1, M){
        long long a, b, w;
        cin >> a >> b >> w; a--, b--;
        E[a].push_back(make_pair(b, w)), E[b].push_back(make_pair(a, w));
    }

    vector<long long> UD = sp1(N, E, U), VD = sp1(N, E, V);

    vector<pair<long long, long long> > SD = sp2(N, E, VD, S), TD = sp2(N, E, VD, T);

    pair<long long, long long> R = make_pair(LONG_LONG_MAX, LONG_LONG_MAX);
    FOR(i, 0, N - 1) {
        R = min(R, make_pair(SD[i].first + TD[i].first, UD[i] + min(SD[i].second, TD[i].second)));
    }
    cout << min(R.second, UD[V]);
}

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