Đường đi ngắn nhất có tổng chẵn
Points
52
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho đồ thị vô hướng có trọng số không âm gồm $N$ đỉnh và $M$ cạnh. Hãy tìm độ dài đường đi ngắn nhất từ đỉnh $1$ đến đỉnh $N$ sao cho tổng trọng số của đường đi là một số chẵn (được phép đi qua một đỉnh hoặc cạnh nhiều lần). Nếu không tồn tại đường đi như vậy, in ra -1.
Dữ liệu vào
- Dòng đầu 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 chứa ba số nguyên $u, v, w$ ($1 \le u, v \le N$, $0 \le w \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là độ dài đường đi ngắn nhất có tổng trọng số chẵn, hoặc
-1.
Ví dụ
| Input | Output |
|---|---|
| 3 3 1 2 2 2 3 3 1 3 6 |
6 |
| 2 1 1 2 3 |
-1 |
Giới hạn
- $1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$
- $0 \le w \le 10^9$
Community Discussion