#include <iostream> #include <vector> #include <algorithm> #include <queue> using namespace std; const long long INF = 1e16; struct Edge { int to, color, cost, id; }; struct Node { long long d; int u, edge_id, color; // Priority queue min-heap bool operator>(const Node& other) const { return d > other.d; } }; // Cấu trúc để quản lý tổng chi phí theo màu tại mỗi đỉnh struct ColorSum { int color; long long sum; }; vector<Edge> adj[100005]; vector<ColorSum> sum_c[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; for (int i = 0; i < m; ++i) { int u, v, c, p; cin >> u >> v >> c >> p; // id chẵn cho chiều u->v, id lẻ cho chiều v->u 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) { // 1. Sắp xếp cạnh theo màu để dùng Two Pointers sort(adj[i].begin(), adj[i].end(), [](const Edge& a, const Edge& b) { return a.color < b.color; }); // 2. Tính tổng chi phí (sum_c) cho mỗi cụm màu tại đỉnh i 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++; } sum_c[i].push_back({adj[i][j].color, s}); 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; // Xuất phát từ đỉnh 1 dist_node[1] = 0; pq.push({0, 1, -1, 0}); // edge_id = -1 nghĩa là trạng thái tự do 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]) { // Tìm sum_c của màu e.color tại u bằng binary search trên vector sum_c đã sort auto it = lower_bound(sum_c[u].begin(), sum_c[u].end(), ColorSum{e.color, 0}, [](const ColorSum& a, const ColorSum& b) { return a.color < b.color; }); long long total_p = it->sum; // Cách 1: Đổi màu duy nhất cạnh e (tốn P_i) -> v trạng thái tự do if (dist_node[e.to] > d + e.cost) { dist_node[e.to] = d + e.cost; pq.push({dist_node[e.to], e.to, -1, 0}); } // Cách 2: Đổi màu tất cả các cạnh khác cùng màu e.color tại u (tốn total_p - P_i) if (dist_node[e.to] > d + total_p - e.cost) { dist_node[e.to] = d + total_p - e.cost; pq.push({dist_node[e.to], e.to, -1, 0}); } // Cách 3: Giữ màu e, chuyển sang trạng thái "nợ" tại v if (dist_edge[e.id] > d) { dist_edge[e.id] = d; pq.push({dist_edge[e.id], e.to, e.id, e.color}); } } } else { // Trạng thái nợ: Vừa đến u bằng cạnh có màu top.color if (d > dist_edge[top.edge_id]) continue; int c = top.color; // Tìm cụm màu c trong adj[u] đã được sort 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; }); auto it_sum = lower_bound(sum_c[u].begin(), sum_c[u].end(), ColorSum{c, 0}, [](const ColorSum& a, const ColorSum& b) { return a.color < b.color; }); long long total_p = (it_sum != sum_c[u].end() && it_sum->color == c) ? it_sum->sum : 0; // Chỉ xét các cạnh cùng màu c tại đỉnh u while (it_adj != adj[u].end() && it_adj->color == c) { // Tránh quay lại cạnh vừa đi (id của cạnh ngược lại là id ^ 1) if (it_adj->id != (top.edge_id ^ 1)) { if (dist_node[it_adj->to] > d + total_p - it_adj->cost) { dist_node[it_adj->to] = d + total_p - it_adj->cost; pq.push({dist_node[it_adj->to], it_adj->to, -1, 0}); } } it_adj++; } } } if (dist_node[n] >= INF) cout << -1 << endl; else cout << dist_node[n] << endl; return 0; }