#include <bits/stdc++.h> using namespace std; const long long INF = 1e16; struct Edge { int to, color, cost, id; long long sum_c; // Tổng chi phí các cạnh cùng màu tại đỉnh bắt đầu }; struct Node { long long d; int u, edge_id; // edge_id = -1: trạng thái thường, >= 0: mã cạnh vừa đi qua bool operator>(const Node& other) const { return d > other.d; } }; vector<Edge> adj[100005]; long long dist_node[100005]; long long dist_edge[200005]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; 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]; 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}); } // Dùng Two Pointers để tính sum_c cho mỗi cụm màu tại từng đỉ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 = adj[i].size(); for (int j = 0; j < sz; ) { int k = j; long long current_sum = 0; while (k < sz && adj[i][k].color == adj[i][j].color) { current_sum += adj[i][k].cost; k++; } // Gán sum_c cho tất cả các cạnh trong cụm màu này for (int l = j; l < k; ++l) adj[i][l].sum_c = current_sum; j = k; } dist_node[i] = INF; } for (int i = 0; i < 2 * m; ++i) dist_edge[i] = INF; priority_queue<Node, vector<Node>, greater<Node>> pq; dist_node[1] = 0; pq.push({0, 1, -1}); while (!pq.empty()) { Node top = pq.top(); pq.pop(); long long d = top.d; int u = top.u; if (top.edge_id == -1) { if (d > dist_node[u]) continue; for (auto& e : adj[u]) { // Cách 1: Đổi màu duy nhất cạnh e (tốn P_i) if (dist_node[e.to] > d + e.cost) { dist_node[e.to] = d + e.cost; pq.push({dist_node[e.to], e.to, -1}); } // Cách 2: Đổi màu các cạnh cùng màu e.color tại u (tốn Sum - P_i) if (dist_node[e.to] > d + e.sum_c - e.cost) { dist_node[e.to] = d + e.sum_c - e.cost; pq.push({dist_node[e.to], e.to, -1}); } // Cách 3: Chuyển sang trạng thái "nợ" (Strategy B) - không tốn phí bây giờ if (dist_edge[e.id] > d) { dist_edge[e.id] = d; pq.push({dist_edge[e.id], e.to, e.id}); } } } else { if (d > dist_edge[top.edge_id]) continue; // Lấy màu của cạnh đã dẫn robot đến u // Cạnh id=k nối (u, v) thì cạnh ngược lại là k^1 nối (v, u) int color_prev = -1; // Ở trạng thái này, robot vừa đi qua cạnh top.edge_id có màu cụ thể. // Ta cần tìm lại màu đó. Để nhanh, hãy lưu color_prev vào State. } } // ...

Main.cpp: In function 'int main()':
Main.cpp:95:6: error: expected '}' at end of input
   95 |     }
      |      ^
Main.cpp:21:12: note: to match this '{'
   21 | int main() {
      |            ^