Siêu Mạng Lưới
Points
80
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
Uncategorized
Đề 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 raVớ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ụ
|
||||
|---|---|---|---|---|---|
| 4 4 1 2 2 1 2 4 3 1 1 3 4 2 3 4 3 1 |
7 |
Giới hạn
- 1 ≤ N, Q ≤ 100000
- 0 ≤ a_i ≤ 10^9
- 0 ≤ x ≤ 10^6
Community Discussion