Submission #1293585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293585		thaibeo417	Robot (JOI21_ho_t4)	C++20	100 / 100	211 ms	65328 KiB

Main

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

using ll = long long;
const ll INF = (ll)4e18;

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

    int N, M;
    if (!(cin >> N >> M)) return 0;

    // V[u] : các cạnh kề với u, lưu (màu, (chi phí P, đỉnh kề))
    vector<vector<pair<int, pair<ll,int>>>> V(N + 1);

    for (int i = 0; i < M; ++i) {
        int a, b, c;
        ll p;
        cin >> a >> b >> c >> p;
        V[a].push_back({c, {p, b}});
        V[b].push_back({c, {p, a}});
    }

    // Số đỉnh tối đa trong đồ thị mở rộng:
    // ban đầu có N đỉnh gốc, thêm tối đa 2*M đỉnh màu-đỉnh
    int maxNodes = N + 2 * M + 5;
    vector<vector<pair<ll,int>>> G(maxNodes); // G[u] : (cost, v)

    int sz = N; // đếm số đỉnh hiện tại trong đồ thị mở rộng

    // Xây đồ thị mở rộng
    for (int u = 1; u <= N; ++u) {
        if (V[u].empty()) continue;

        // Gom các cạnh theo màu
        auto &vec = V[u];
        sort(vec.begin(), vec.end(),
             [](const auto &A, const auto &B) {
                 if (A.first != B.first) return A.first < B.first;
                 // phụ cho ổn định, không bắt buộc
                 return A.second.second < B.second.second;
             });

        int nAdj = (int)vec.size();
        int l = 0;
        while (l < nAdj) {
            int r = l;
            int color = vec[l].first;
            ll sumP = 0;

            // [l, r) là nhóm cùng màu "color" tại đỉnh u
            while (r < nAdj && vec[r].first == color) {
                sumP += vec[r].second.first;
                ++r;
            }

            int cnt = r - l;

            if (cnt == 1) {
                // Chỉ có 1 cạnh màu này ở u:
                // đi qua cạnh này từ u sang v với cost 0
                int v = vec[l].second.second;
                G[u].push_back({0, v});
            } else {
                // Có >= 2 cạnh cùng màu tại u
                // tạo đỉnh trung gian nodeColor = (u, color)
                int nodeColor = ++sz;

                // từ u sang nodeColor (chuẩn bị thực hiện move Y) với cost 0
                G[u].push_back({0, nodeColor});

                // duyệt từng cạnh trong nhóm
                for (int j = l; j < r; ++j) {
                    ll p = vec[j].second.first;
                    int v = vec[j].second.second;

                    // 1) di chuyển kiểu X: tô riêng cạnh này, từ u sang v, cost = p
                    G[u].push_back({p, v});

                    // 2) bước X của cặp (X,Y): từ v sang nodeColor với cost 0
                    G[v].push_back({0, nodeColor});

                    // 3) bước Y: từ nodeColor sang v, cost = tổng P các cạnh cùng màu trừ cạnh này
                    G[nodeColor].push_back({sumP - p, v});
                }
            }

            l = r;
        }
    }

    // Dijkstra trên đồ thị mở rộng
    vector<ll> dist(sz + 1, INF);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;

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

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d != dist[u]) continue;

        for (auto [w, v] : G[u]) {
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }

    if (dist[N] == INF) cout << -1;
    else cout << dist[N];

    return 0;
}

• Subtask 1: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42