Submission #1180661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180661		nekolie	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	345 ms	18616 KiB

commuter_pass

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,m; cin >> n >> m;
    int S, T, U, V, a, b, c;
    cin >> S >> T >> U >> V;
    vector<pair<int,int>> g[n+1];
    for (int i = 0; i < m; i++)
        cin >> a >> b >> c, g[a].push_back({b,c}), g[b].push_back({a,c});
    bool odw1[n+1], odw2[n+1][3]; fill(odw1,odw1+n+1,false);
    long long odl1[n+1][2], odl2[n+1][3], odp = 1000000000000000000;
    for (int i = 1; i <= n; i++)
        odl1[i][0] = odl1[i][1] = odl2[i][0] = odl2[i][1] = odl2[i][2] = 1000000000000000000;
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> q1;
    q1.push({0,S}), odl1[S][0] = 0;
    while (!q1.empty()) {
        long long d = q1.top().first; int v = q1.top().second;
        q1.pop();
        if (odw1[v])
            continue;
        odw1[v] = true;
        for (int i = 0; i < g[v].size(); i++)
            if (odl1[v][0]+g[v][i].second < odl1[g[v][i].first][0])
                odl1[g[v][i].first][0] = odl1[v][0]+g[v][i].second, q1.push({odl1[v][0]+g[v][i].second,g[v][i].first});
    }
    fill(odw1,odw1+n+1,false), odl1[T][1] = 0, q1.push({0,T});
    while (!q1.empty()) {
        long long d = q1.top().first; int v = q1.top().second;
        q1.pop();
        if (odw1[v])
            continue;
        odw1[v] = true;
        for (int i = 0; i < g[v].size(); i++)
            if (odl1[v][1]+g[v][i].second < odl1[g[v][i].first][1])
                odl1[g[v][i].first][1] = odl1[v][1]+g[v][i].second, q1.push({odl1[v][1]+g[v][i].second,g[v][i].first});
    }
    priority_queue<tuple<long long,int,int>,vector<tuple<long long,int,int>>,greater<tuple<long long,int,int>>> q;
    q.push({0,U,0}), odl2[U][0] = 0;
    for (int i = 1; i <= n; i++)
        odw2[i][0] = odw2[i][1] = odw2[i][2] = false;
    while (!q.empty()) {
        long long d = get<0>(q.top());
        int v = get<1>(q.top()), t = get<2>(q.top()); q.pop();
        if (odw2[v][t])
            continue;
        odw2[v][t] = true;
        if (t == 0 && odl1[T][0] == odl1[v][0]+odl1[v][1] && odl2[v][1] > d)
            odl2[v][1] = d, q.push({d,v,1});
        else if (t == 1 && odl2[v][2] > d)
            odl2[v][2] = d, q.push({d,v,2});
        for (int i = 0; i < g[v].size(); i++) {
            if (t == 1 && odl1[v][1] == g[v][i].second+odl1[g[v][i].first][1] && odl2[v][t] < odl2[g[v][i].first][t] && odl1[T][0] == odl1[g[v][i].first][0]+odl1[g[v][i].first][1])
                odl2[g[v][i].first][t] = odl2[v][t], q.push({odl2[v][t],g[v][i].first,t});
            else if (t != 1 && odl2[v][t]+g[v][i].second < odl2[g[v][i].first][t])
                odl2[g[v][i].first][t] = odl2[v][t]+g[v][i].second, q.push({odl2[g[v][i].first][t],g[v][i].first,t});
        }
    }
    odp = min(odl2[V][0],odl2[V][2]);
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 3; j++)
            odl2[i][j] = 1000000000000000000, odw2[i][j] = false;
    q.push({0,U,0}), odl2[U][0] = 0;
    while (!q.empty()) {
        long long d = get<0>(q.top());
        int v = get<1>(q.top()), t = get<2>(q.top()); q.pop();
        if (odw2[v][t])
            continue;
        odw2[v][t] = true;
        if (t == 0 && odl1[T][0] == odl1[v][0]+odl1[v][1] && odl2[v][1] > d)
            odl2[v][1] = d, q.push({d,v,1});
        else if (t == 1 && odl2[v][2] > d)
            odl2[v][2] = d, q.push({d,v,2});
        for (int i = 0; i < g[v].size(); i++) {
            if (t == 1 && odl1[v][0] == g[v][i].second+odl1[g[v][i].first][0] && odl2[v][t] < odl2[g[v][i].first][t] && odl1[T][0] == odl1[g[v][i].first][0]+odl1[g[v][i].first][1])
                odl2[g[v][i].first][t] = odl2[v][t], q.push({odl2[v][t],g[v][i].first,t});
            else if (t != 1 && odl2[v][t]+g[v][i].second < odl2[g[v][i].first][t])
                odl2[g[v][i].first][t] = odl2[v][t]+g[v][i].second, q.push({odl2[g[v][i].first][t],g[v][i].first,t});
        }
    }
    odp = min(odp,min(odl2[V][0],odl2[V][2]));
    cout << odp << endl;
}

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