Submission #646105

#	Time	Username	Problem	Language	Result	Execution time	Memory
646105		Alexandruabcde	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	500 ms	27948 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair <LL, int> PLLI;
typedef pair <LL, pair <int, int> > PLLII;

constexpr int NMAX = 1e5 + 5;
constexpr LL INF = 1LL * 1e17;

int N, M, S, T, U, V;

vector <PLLI> G[NMAX];

LL Dist_U[NMAX];
LL Dist_V[NMAX];

bool viz[NMAX];

LL ans = INF;

LL Dist[2][NMAX];
LL dp[2][NMAX];

void Dijkstra (int start, LL who[]) {
    memset(viz, 0, sizeof(viz));
    for (int i = 1; i <= N; ++ i )
        who[i] = -1;

    priority_queue <PLLI, vector <PLLI>, greater <PLLI> > H;

    H.push({0, start});

    while (!H.empty()) {
        int node = H.top().second;
        LL cost = H.top().first;

        H.pop();

        if (viz[node]) continue;

        viz[node] = true;
        who[node] = cost;

        for (auto it : G[node]) {
            H.push({cost + it.first, it.second});
        }
    }
}

LL Total_Dist[NMAX];
void Answer (int st, int en) {
    memset(viz, 0, sizeof(viz));
    memset(Total_Dist, 0, sizeof(Total_Dist));

    for (int i = 1; i <= N; ++ i ) {
        Total_Dist[i] = INF;
        for (int j = 0; j < 2; ++ j )
            dp[j][i] = 0;
    }

    priority_queue <PLLII, vector <PLLII>, greater <PLLII> > H;

    dp[0][0] = dp[1][0] = INF;

    H.push({0, {st, 0}});

    while (!H.empty()) {
        LL cost = H.top().first;

        int node = H.top().second.first;
        int parent = H.top().second.second;

        H.pop();

        if (viz[node]) {
            if (Total_Dist[node] < cost) continue;

            LL to[2];

            for (int j = 0; j < 2; ++ j )
                to[j] = min(dp[j][parent], Dist[j][node]);

            if (to[0] + to[1] <= dp[0][node] + dp[1][node]) {
                for (int j = 0; j < 2; ++ j )
                    dp[j][node] = to[j];
            }
            continue;
        }

        viz[node] = true;
        Total_Dist[node] = cost;

        for (int j = 0; j < 2; ++ j )
            dp[j][node] = min(dp[j][parent], Dist[j][node]);

        for (auto it : G[node])
            H.push({cost + it.first, {it.second, node}});
    }

    ans = min(ans, dp[0][en] + dp[1][en]);
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M >> S >> T >> U >> V;

    for (int i = 1; i <= M; ++ i ) {
        int x, y;
        LL c;

        cin >> x >> y >> c;

        G[x].push_back({c, y});
        G[y].push_back({c, x});
    }

    Dijkstra(U, Dist[0]);
    Dijkstra(V, Dist[1]);

    ans = Dist[0][V];

    Answer(S, T);
    Answer(T, S);

    cout << ans << '\n';

    return 0;
}

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