#include <bits/stdc++.h> using namespace std; const long long INF = 1e16; struct Edge { int to, color, cost, id; }; struct State { long long d; int u, c; // c = 0: trạng thái thường, c > 0: mã định danh trạng thái màu bool operator>(const State& other) const { return d > other.d; } }; vector<Edge> adj[100005]; // sum_c[u][color] -> dùng vector + pair để thay map vector<pair<int, long long>> sum_c[100005]; // dist[u] lưu khoảng cách trạng thái thường long long dist0[100005]; // dist_c[edge_id] lưu khoảng cách khi robot vừa đi qua cạnh id (Strategy B) long long dist_c[400005]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int i = 0; i < m; ++i) { int u, v, c, p; cin >> u >> v >> c >> p; // Mỗi cạnh 2 chiều, gán id để định danh trạng thái (u, color) adj[u].push_back({v, c, p, i * 2}); adj[v].push_back({u, c, p, i * 2 + 1}); } 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; }); // Tính sum_c tối ưu for (int j = 0; j < adj[i].size(); ) { int k = j; long long s = 0; while (k < adj[i].size() && adj[i][k].color == adj[i][j].color) { s += adj[i][k].cost; k++; } sum_c[i].push_back({adj[i][j].color, s}); j = k; } dist0[i] = INF; } for (int i = 0; i < 2 * m; ++i) dist_c[i] = INF; priority_queue<State, vector<State>, greater<State>> pq; dist0[1] = 0; pq.push({0, 1, -1}); // c = -1 đại diện cho trạng thái dist0 while (!pq.empty()) { State top = pq.top(); pq.pop(); if (top.c == -1) { if (top.d > dist0[top.u]) continue; int u = top.u; for (auto& e : adj[u]) { // Lấy tổng cost của màu e.color tại u long long total_p = 0; auto it = lower_bound(sum_c[u].begin(), sum_c[u].end(), make_pair(e.color, -1LL)); total_p = it->second; // 1. Đổi màu cạnh e: cost = e.cost if (dist0[e.to] > top.d + e.cost) { dist0[e.to] = top.d + e.cost; pq.push({dist0[e.to], e.to, -1}); } // 2. Đổi màu các cạnh khác cùng màu e.color: cost = total_p - e.cost if (dist0[e.to] > top.d + total_p - e.cost) { dist0[e.to] = top.d + total_p - e.cost; pq.push({dist0[e.to], e.to, -1}); } // 3. Vào trạng thái đặc biệt của cạnh e (Strategy B) if (dist_c[e.id] > top.d) { dist_c[e.id] = top.d; pq.push({dist_c[e.id], e.to, e.id}); } } } else { // Đang ở trạng thái đặc biệt sau khi đi qua cạnh e_id_prev if (top.d > dist_c[top.c]) continue; int u = top.u; // Lấy màu của cạnh đã đưa ta đến đây int prev_id = top.c; int color_prev = (prev_id % 2 == 0) ? adj[adj[u][0].to][prev_id/2].color : -1; // Cần lấy lại color từ ID // Cách tốt hơn: Lưu color trực tiếp vào State // Tuy nhiên, để tối ưu, ta chỉ duyệt các cạnh cùng màu tại u // Tìm lại color_prev từ ID gốc (cách nhanh: lưu color vào struct Edge) // Ở đây mình sẽ duyệt các cạnh cùng màu với cạnh đã đi int target_color = 0; // Tìm color của cạnh có id = prev_id (cạnh ngược lại là prev_id ^ 1) // Nhưng thực tế ta có thể lưu color vào State để tránh tìm kiếm } } // ... (logic Dijkstra tiếp tục)

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