Submission #1153620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153620		minhpk	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	374 ms	64640 KiB

commuter_pass

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

const int INF = 1e18;
int a, b, s, t, u, v;
vector<pair<int, int>> z[200005]; // Tăng kích thước cho an toàn
int cnt1[200005], cnt2[200005];
int cnt[200005][3];

struct Node {
    int nxt, val, fri;
};

vector<Node> z1[200005], z2[200005];

struct Node1 {
    int val1, pos1, type;
    bool operator>(const Node1 &other) const {
        return val1 > other.val1;
    }
};

void dijkstra_single_source(int src, int dist[]) {
    fill(dist, dist + a + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [val, pos1] = pq.top();
        pq.pop();

        if (val > dist[pos1]) continue;

        for (auto [nxt, w] : z[pos1]) {
            if (dist[nxt] > val + w) {
                dist[nxt] = val + w;
                pq.push({dist[nxt], nxt});
            }
        }
    }
}

void dijkstra_multi_state(int src, vector<Node> adj[], int dist[][3]) {
    for (int i = 1; i <= a; i++) {
        for (int j = 0; j < 3; j++) {
            dist[i][j] = INF;
        }
    }

    priority_queue<Node1, vector<Node1>, greater<Node1>> pq;
    dist[src][0] = 0;
    pq.push({0, src, 0});

    while (!pq.empty()) {
        auto [val, pos1, type] = pq.top();
        pq.pop();

        if (val > dist[pos1][type]) continue;

        for (auto [nxt, w, fri] : adj[pos1]) {
            if (type == 0) {
                if (dist[nxt][type] > val + w) {
                    dist[nxt][type] = val + w;
                    pq.push({dist[nxt][type], nxt, type});
                }
                if (fri == 0 && dist[nxt][1] > val) {
                    dist[nxt][1] = val;
                    pq.push({dist[nxt][1], nxt, 1});
                }
            } else if (type == 1) {
                if (fri == 0 && dist[nxt][1] > val) {
                    dist[nxt][1] = val;
                    pq.push({dist[nxt][1], nxt, 1});
                }
                if (dist[nxt][2] > val + w) {
                    dist[nxt][2] = val + w;
                    pq.push({dist[nxt][2], nxt, 2});
                }
            } else {
                if (dist[nxt][type] > val + w) {
                    dist[nxt][type] = val + w;
                    pq.push({dist[nxt][type], nxt, type});
                }
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> a >> b >> s >> t >> u >> v;

    for (int i = 0; i < b; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        z[x].emplace_back(y, w);
        z[y].emplace_back(x, w);
    }

    dijkstra_single_source(s, cnt1);
    dijkstra_single_source(t, cnt2);

    for (int i = 1; i <= a; i++) {
        for (auto [y, val] : z[i]) {
            int chisoan = (cnt1[i] + cnt2[y] + val == cnt1[t]) ? 0 : -1;
            int chisoan1 = (cnt1[y] + cnt2[i] + val == cnt1[t]) ? 0 : -1;
            z2[i].push_back({y, val, chisoan1});
            z1[i].push_back({y, val, chisoan});
        }
    }

    dijkstra_multi_state(u, z1, cnt);
    int min1 = min({cnt[v][0], cnt[v][1], cnt[v][2]});
    dijkstra_multi_state(u, z2, cnt);
    min1 = min({min1, cnt[v][0], cnt[v][1], cnt[v][2]});

    cout << min1 << "\n";
    return 0;
}

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