Siêu Mạng Lưới

Buổi 42 — LCA & Binary Lifting Buổi 45 — Heavy-Light Decomposition Buổi 52 — Mock Contest Phase 2
Points
80
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Một hệ thống giao thông gồm $N$ trạm trung chuyển (đánh số từ $1$ đến $N$) và $M$ tuyến đường hai chiều. Tuyến đường thứ $i$ nối giữa hai trạm $u_i$ và $v_i$, mất thời gian di chuyển $w_i$ và được gắn nhãn màu $c_i$. Để tránh hiện tượng quá tải cùng một hãng vận hành, hành khách di chuyển từ trạm $1$ đến trạm $N$ phải tuân thủ quy tắc: không được đi qua hai tuyến đường liên tiếp có cùng màu (có thể đi qua cùng một đỉnh hoặc cùng một tuyến nếu thỏa mãn điều kiện màu sắc).

Hãy tìm tổng thời gian nhỏ nhất để đi từ trạm $1$ đến trạm $N$ theo đúng quy tắc trên, hoặc in ra -1 nếu không tồn tại hành trình hợp lệ.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, M$ ($1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$).
  • $M$ dòng tiếp theo, mỗi dòng gồm bốn số nguyên $u_i, v_i, w_i, c_i$ ($1 \le u_i, v_i \le N$, $u_i \ne v_i$, $1 \le w_i \le 10^9$, $1 \le c_i \le 10^9$).
Dữ liệu ra

In ra tổng thời gian ngắn nhất từ $1$ đến $N$, hoặc -1 nếu không đi được.

Ví dụ
Input Output
Dữ liệu ra

Với mỗi truy vấn loại 2 hoặc 3, in ra kết quả trên một dòng.

Ví dụ
Input Output
5 5\n1 2 3 4 5\n1 2\n1 3\n2 4\n2 5\n2 4 5\n1 2 5 1\n2 4 5\n3 1\n3 2
4 4
1 2 2 1
2 4 3 1
1 3 4 2
3 4 3 1
7
7\n10\n21\n12
Giới hạn
  • 1 ≤ N, Q ≤ 100000
  • 0 ≤ a_i ≤ 10^9
  • 0 ≤ x ≤ 10^6
Draft saved