#include <iostream> #include <vector> #include <algorithm> #include <queue> using namespace std; // Sử dụng long long cho khoảng cách để tránh tràn số const long long INF = 1e16; struct Edge { int to, color, p, id; }; struct State { long long d; int u, edge_id; // edge_id = -1: trạng thái tại đỉnh u, >=0: trạng thái đặc biệt tại cạnh bool operator>(const State& other) const { return d > other.d; } }; // Mảng lưu trữ dữ liệu vector<Edge> adj[100005]; vector<pair<int, long long>> color_sums[100005]; long long dist_node[100005]; long long dist_special[200005]; int main() { // Tối ưu hóa nhập xuất ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; if (!(cin >> n >> m)) return 0; // Lưu thông tin cạnh ban đầu vector<int> U(m), V(m), C(m), P(m); for (int i = 0; i < m; ++i) { cin >> U[i] >> V[i] >> C[i] >> P[i]; // id chẵn: U->V, id lẻ: V->U adj[U[i]].push_back({V[i], C[i], P[i], i * 2}); adj[V[i]].push_back({U[i], C[i], P[i], i * 2 + 1}); } // Tiền xử lý: Sắp xếp và tính tổng chi phí theo màu tại mỗi đỉnh for (int i = 1; i <= n; ++i) { sort(adj[i].begin(), adj[i].end(), [](const Edge& a, const Edge& b) { return a.color < b.color; }); int sz = (int)adj[i].size(); for (int j = 0; j < sz; ) { int k = j; long long s = 0; while (k < sz && adj[i][k].color == adj[i][j].color) { s += adj[i][k].cost; k++; } color_sums[i].push_back({adj[i][j].color, s}); j = k; } dist_node[i] = INF; } for (int i = 0; i < 2 * m; ++i) dist_special[i] = INF; priority_queue<State, vector<State>, greater<State>> pq; dist_node[1] = 0; pq.push({0, 1, -1}); while (!pq.empty()) { State top = pq.top(); pq.pop(); if (top.edge_id == -1) { if (top.d > dist_node[top.u]) continue; int u = top.u; for (auto& e : adj[u]) { // Tìm tổng chi phí của màu hiện tại tại đỉnh u auto it = lower_bound(color_sums[u].begin(), color_sums[u].end(), make_pair(e.color, -1LL)); long long total_p = it->second; // 1. Đổi màu duy nhất cạnh này (Strategy A) if (dist_node[e.to] > top.d + e.p) { dist_node[e.to] = top.d + e.p; pq.push({dist_node[e.to], e.to, -1}); } // 2. Đổi màu tất cả các cạnh khác cùng màu (Strategy B) if (dist_node[e.to] > top.d + total_p - e.p) { dist_node[e.to] = top.d + total_p - e.p; pq.push({dist_node[e.to], e.to, -1}); } // 3. Chuyển sang trạng thái đặc biệt: đến e.to nhưng chưa tính phí đổi màu tại u if (dist_special[e.id] > top.d) { dist_special[e.id] = top.d; pq.push({dist_special[e.id], e.to, e.id}); } } } else { // Trạng thái đặc biệt: đang ở đỉnh u, vừa đi qua cạnh top.edge_id if (top.d > dist_special[top.edge_id]) continue; int u = top.u; // Cạnh vừa đi qua là top.edge_id, cạnh ngược lại của nó là top.edge_id ^ 1 // Cần lấy màu của cạnh này (có thể lưu trữ thêm hoặc tìm trong adj) // Để tối ưu, ta đã lưu ID chẵn/lẻ. Cạnh đi từ u ra có màu ta cần. // Truy xuất màu của cạnh id gốc: int original_edge_idx = top.edge_id / 2; int c = C[original_edge_idx]; auto it_sum = lower_bound(color_sums[u].begin(), color_sums[u].end(), make_pair(c, -1LL)); long long total_p = it_sum->second; // Chỉ duyệt các cạnh có cùng màu c tại đỉnh u auto it_adj = lower_bound(adj[u].begin(), adj[u].end(), Edge{0, c, 0, 0}, [](const Edge& a, const Edge& b) { return a.color < b.color; }); while (it_adj != adj[u].end() && it_adj->color == c) { // Không quay ngược lại cạnh vừa đi (id ^ 1) if (it_adj->id != (top.edge_id ^ 1)) { if (dist_node[it_adj->to] > top.d + total_p - it_adj->p) { dist_node[it_adj->to] = top.d + total_p - it_adj->p; pq.push({dist_node[it_adj->to], it_adj->to, -1}); } } it_adj++; } } } if (dist_node[n] >= INF) cout << -1 << endl; else cout << dist_node[n] << endl; return 0; }

Main.cpp: In function 'int main()':
Main.cpp:58:32: error: '__gnu_cxx::__alloc_traits<std::allocator<Edge>, Edge>::value_type' {aka 'struct Edge'} has no member named 'cost'
   58 |                 s += adj[i][k].cost;
      |                                ^~~~