제출 #1304122

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1304122		duongquanghai08	Robot (JOI21_ho_t4)	C++20	0 / 100	36 ms	10212 KiB

Main

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

const long long INF = 1e18;

struct Edge {
    int to;
    int id;
    int color;
    int cost;
};

struct State {
    long long dist;
    int u;
    int edge_id; // 0: cơ bản, >0: trạng thái tạm từ cạnh edge_id
    
    bool operator>(const State& other) const {
        return dist > other.dist;
    }
};

int N, M;
vector<Edge> adj[100005];
// map<int, long long> sum_color_cost[100005]; // Dùng vector sort thay map để tối ưu
vector<pair<int, long long>> sum_c[100005];

// Distance array
// dist[u] lưu trạng thái cơ bản
// dist_edge[i] lưu trạng thái tạm: vừa đi qua cạnh i (theo hướng vào đỉnh mục tiêu của cạnh i)
// Cạnh i nối u-v. Ta quy ước id từ 1..M.
// Để phân biệt hướng, ta dùng index: i (hướng u->v) và i+M (hướng v->u)?
// Trong input cạnh i nối A[i] và B[i].
// Khi duyệt adj[u], nếu cạnh có id là k nối u->v. Trạng thái tạm tại v là k.
// Trạng thái tạm tại u (từ v về) cũng là k? Không được trùng.
// Do đó ta dùng chỉ số cạnh trong adj list hoặc map riêng.
// Cách tốt nhất: Vì ta dùng Dijkstra, ta chỉ cần ID của cạnh.
// dist_edge[i] lưu chi phí nhỏ nhất để đến B[i] từ A[i] thông qua cạnh i.
// dist_edge[i + M] lưu chi phí nhỏ nhất để đến A[i] từ B[i] thông qua cạnh i.
long long dist_node[100005];
long long dist_edge[400005]; // 1..M: A->B, M+1..2M: B->A

long long get_sum_color(int u, int color) {
    auto it = lower_bound(sum_c[u].begin(), sum_c[u].end(), make_pair(color, -1LL));
    if (it != sum_c[u].end() && it->first == color) {
        return it->second;
    }
    return 0;
}

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

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

    vector<tuple<int, int, int, int>> edges_input;
    edges_input.reserve(M + 1);
    edges_input.push_back({0,0,0,0});

    for (int i = 1; i <= M; i++) {
        int u, v, c, p;
        cin >> u >> v >> c >> p;
        adj[u].push_back({v, i, c, p});
        adj[v].push_back({u, i, c, p});
        edges_input.push_back({u, v, c, p});
    }

    // Precompute sum_color_cost
    for (int u = 1; u <= N; u++) {
        sort(adj[u].begin(), adj[u].end(), [](const Edge& a, const Edge& b) {
            return a.color < b.color;
        });
        
        long long current_sum = 0;
        int current_c = -1;
        
        for (const auto& e : adj[u]) {
            if (e.color != current_c) {
                if (current_c != -1) sum_c[u].push_back({current_c, current_sum});
                current_c = e.color;
                current_sum = 0;
            }
            current_sum += e.cost;
        }
        if (current_c != -1) sum_c[u].push_back({current_c, current_sum});
    }

    // Dijkstra
    priority_queue<State, vector<State>, greater<State>> pq;

    fill(dist_node, dist_node + N + 1, INF);
    fill(dist_edge, dist_edge + 2 * M + 1, INF);

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

    while (!pq.empty()) {
        State top = pq.top();
        pq.pop();

        long long d = top.dist;
        int u = top.u;
        int from_edge_idx = top.edge_id; // 0 nếu là node, >0 nếu là edge

        if (from_edge_idx == 0) {
            if (d > dist_node[u]) continue;
            if (u == N) {
                cout << d << endl;
                return 0;
            }

            // Từ trạng thái cơ bản (u), đi sang các hàng xóm
            for (const auto& e : adj[u]) {
                int v = e.to;
                int c = e.color;
                int p = e.cost;
                int idx = e.id;
                
                long long sum_p = get_sum_color(u, c);

                // Option 1: Đổi màu cạnh này (Cost P) -> Đến Node v
                if (dist_node[v] > d + p) {
                    dist_node[v] = d + p;
                    pq.push({dist_node[v], v, 0});
                }

                // Option 2: Giữ cạnh này, đổi các cạnh khác (Cost Sum - P) -> Đến Node v
                // Chỉ làm nếu Sum - P < P (tối ưu hóa) hoặc cứ push vào
                if (dist_node[v] > d + sum_p - p) {
                    dist_node[v] = d + sum_p - p;
                    pq.push({dist_node[v], v, 0});
                }

                // Option 3: Giữ cạnh này, không trả phí ngay (Cost 0) -> Đến Edge State (v, từ u qua idx)
                // Cần xác định index cho dist_edge.
                // Nếu A->B (u là A), dùng idx. Nếu B->A (u là B), dùng idx + M.
                int edge_state_idx = (u == get<0>(edges_input[idx])) ? idx : idx + M;
                
                if (dist_edge[edge_state_idx] > d) {
                    dist_edge[edge_state_idx] = d;
                    pq.push({dist_edge[edge_state_idx], v, edge_state_idx});
                }
            }
        } else {
            // Đang ở trạng thái tạm tại u, vừa đến từ cạnh `from_edge_idx`
            // Cạnh này thực tế là edge_id gốc `real_idx`
            int real_idx = (from_edge_idx > M) ? from_edge_idx - M : from_edge_idx;
            // Cạnh này có màu C, phí P.
            // Lưu ý: u là đỉnh hiện tại. Cạnh real_idx nối u và v_prev.
            int v_prev = (u == get<0>(edges_input[real_idx])) ? get<1>(edges_input[real_idx]) : get<0>(edges_input[real_idx]);
            int c_in = get<2>(edges_input[real_idx]);
            int p_in = get<3>(edges_input[real_idx]);

            if (d > dist_edge[from_edge_idx]) continue;

            long long sum_p_in = get_sum_color(u, c_in);

            // Transition 1: Chuyển về trạng thái cơ bản tại u
            // Cost: Đổi tất cả các cạnh màu C_in tại u ngoại trừ cạnh vừa đi vào.
            long long cost_to_base = sum_p_in - p_in;
            if (dist_node[u] > d + cost_to_base) {
                dist_node[u] = d + cost_to_base;
                pq.push({dist_node[u], u, 0});
            }

            // Transition 2: Tiếp tục đi sang cạnh khác cùng màu C_in (Hub trick)
            // Thay vì duyệt edges, ta chỉ cần cost để vào Hub.
            // Nhưng ở đây không có node Hub tường minh trong struct State.
            // Ta thực hiện logic Hub: Từ trạng thái tạm này, ta có thể đến bất kỳ Node v' nào
            // nối với u bằng màu C_in với chi phí (Sum_p_in - p_in).
            // (Sum_p_in - p_in) chính là cost_to_base.
            // NHƯNG, nếu đi qua Hub, khi đến v', ta đang ở trạng thái CƠ BẢN của v' (vì đã giải quyết xong u).
            // Đợi đã, logic Hub:
            // Path: v_prev --(c_in)--> u --(c_in)--> v_next
            // Cost thực tế: (Sum_p_in - p_in - p_next) + p_next (phí qua p_next??)
            // Không, logic là: giữ màu c_in cho CẢ HAI cạnh.
            // Vậy ta phải đổi màu tất cả các cạnh màu c_in tại u NGOẠI TRỪ cạnh vào và cạnh ra.
            // Cost = Sum_p_in - p_in - p_next.
            // Sau khi trả phí này, ta đi qua v_next và đến trạng thái CƠ BẢN tại v_next?
            // Đúng, vì tại u đã xử lý xong.
            
            // Tìm các cạnh cùng màu c_in trong adj[u]
            // Để tối ưu, sum_c đã sort edges theo màu, hoặc adj đã sort.
            // Ta dùng binary search hoặc con trỏ để tìm range màu c_in trong adj[u].
            
            // Tìm range trong adj[u]
            auto it_start = lower_bound(adj[u].begin(), adj[u].end(), c_in, [](const Edge& e, int val) {
                return e.color < val;
            });
            
            while (it_start != adj[u].end() && it_start->color == c_in) {
                int v_next = it_start->to;
                int p_next = it_start->cost;
                
                // Không quay lại đường cũ
                if (it_start->id != real_idx) {
                    long long move_cost = sum_p_in - p_in - p_next;
                    if (dist_node[v_next] > d + move_cost) {
                        dist_node[v_next] = d + move_cost;
                        pq.push({dist_node[v_next], v_next, 0});
                    }
                }
                it_start++;
            }
        }
    }

    cout << -1 << endl;
    return 0;
}

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