Submission #1269638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269638		bnd2100	Robot (JOI21_ho_t4)	C++20	0 / 100	3093 ms	5136 KiB

Main

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

const long long INF = 1e18; // Sử dụng giá trị lớn cho vô cùng

struct Road {
    int u, v, id; // id là chỉ số của con đường trong mảng roads_data
    int initial_color;
    int cost_to_change;
};

struct State {
    long long cost;
    int node;

    bool operator>(const State& other) const {
        return cost > other.cost;
    }
};

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

    int N, M;
    cin >> N >> M;

    vector<Road> roads_data(M);
    // adj[node] lưu danh sách các cặp {neighbor_node, road_id}
    vector<vector<pair<int, int>>> adj(N + 1); 

    for (int i = 0; i < M; ++i) {
        int u, v, c, p;
        cin >> u >> v >> c >> p;
        roads_data[i] = {u, v, i, c, p};
        adj[u].push_back({v, i});
        adj[v].push_back({u, i}); // Đường đi hai chiều
    }

    vector<long long> dist(N + 1, INF);
    priority_queue<State, vector<State>, greater<State>> pq;

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

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

        long long current_cost = current.cost;
        int u = current.node;

        if (current_cost > dist[u]) {
            continue;
        }

        // Duyệt qua tất cả các màu có thể (1 đến M)
        // Giả sử chúng ta muốn nói màu 'target_color' từ node 'u'
        for (int target_color = 1; target_color <= M; ++target_color) {
            long long cost_to_make_move = 0;
            int potential_next_node = -1; // Node mà chúng ta sẽ đến nếu nói target_color
            bool possible_move = true; // Có thể thực hiện nước đi này không

            // Liệt kê tất cả các con đường xuất phát từ 'u'
            vector<int> roads_from_u_indices;
            for (auto& edge : adj[u]) {
                roads_from_u_indices.push_back(edge.second);
            }

            // Bước 1: Tìm con đường tiềm năng duy nhất để đi
            // Nếu có nhiều đường màu target_color, hoặc đường đó không dẫn đến một node duy nhất,
            // thì chúng ta phải thay đổi màu của các đường thừa.

            // Cách tính chi phí cho mỗi màu 'target_color' từ 'u':
            // Chúng ta muốn có duy nhất một con đường 'X' xuất phát từ 'u' có màu 'target_color',
            // và các con đường khác đều không có màu 'target_color'.

            vector<pair<int, int>> roads_with_target_color_from_u; // {road_idx, neighbor_node}

            for (int road_idx : roads_from_u_indices) {
                Road& r = roads_data[road_idx];
                int neighbor_node = (r.u == u) ? r.v : r.u;

                if (r.initial_color == target_color) {
                    roads_with_target_color_from_u.push_back({road_idx, neighbor_node});
                }
            }

            // Trường hợp 1: Không có con đường nào ban đầu có màu target_color
            //   Chúng ta phải chọn một con đường và thay đổi màu của nó.
            //   Để tối ưu, chúng ta sẽ chọn con đường có chi phí thay đổi thấp nhất.
            if (roads_with_target_color_from_u.empty()) {
                long long min_change_cost_to_create_path = INF;
                int best_road_idx_to_change = -1;

                for (int road_idx : roads_from_u_indices) {
                    Road& r = roads_data[road_idx];
                    if (r.cost_to_change < min_change_cost_to_create_path) {
                        min_change_cost_to_create_path = r.cost_to_change;
                        best_road_idx_to_change = road_idx;
                    }
                }

                if (best_road_idx_to_change != -1) {
                    cost_to_make_move += min_change_cost_to_create_path;
                    Road& best_r = roads_data[best_road_idx_to_change];
                    potential_next_node = (best_r.u == u) ? best_r.v : best_r.u;
                } else {
                    possible_move = false; // Không có đường nào để thay đổi màu
                }
            }
            // Trường hợp 2: Có một hoặc nhiều con đường ban đầu có màu target_color
            else {
                // Nếu có 1 con đường ban đầu có màu target_color
                if (roads_with_target_color_from_u.size() == 1) {
                    potential_next_node = roads_with_target_color_from_u[0].second;
                    // Không cần thay đổi màu của nó, chi phí là 0 cho đường này
                }
                // Nếu có nhiều hơn 1 con đường ban đầu có màu target_color
                else {
                    // Tìm con đường có chi phí thay đổi thấp nhất để giữ lại làm màu target_color,
                    // và thay đổi màu của các con đường còn lại.
                    long long min_cost_to_keep_one = INF;
                    int best_road_to_keep_idx = -1;
                    int best_road_to_keep_neighbor = -1;

                    for (auto& p : roads_with_target_color_from_u) {
                        int road_idx = p.first;
                        int neighbor = p.second;
                        Road& r = roads_data[road_idx];

                        long long current_temp_cost = 0;
                        for (auto& other_p : roads_with_target_color_from_u) {
                            int other_road_idx = other_p.first;
                            if (other_road_idx != road_idx) {
                                current_temp_cost += roads_data[other_road_idx].cost_to_change;
                            }
                        }
                        if (current_temp_cost < min_cost_to_keep_one) {
                            min_cost_to_keep_one = current_temp_cost;
                            best_road_to_keep_idx = road_idx;
                            best_road_to_keep_neighbor = neighbor;
                        }
                    }
                    cost_to_make_move += min_cost_to_keep_one;
                    potential_next_node = best_road_to_keep_neighbor;
                }
            }

            // Nếu có một nước đi hợp lệ với chi phí đã tính
            if (possible_move && potential_next_node != -1) {
                if (current_cost + cost_to_make_move < dist[potential_next_node]) {
                    dist[potential_next_node] = current_cost + cost_to_make_move;
                    pq.push({dist[potential_next_node], potential_next_node});
                }
            }
        }
    }

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

    return 0;
}

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