Con Đường Ngắn Thứ Hai
Points
18
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Cho đồ thị vô hướng có trọng số dương gồm $N$ đỉnh và $M$ cạnh. Một đường đi (cho phép đi lặp lại đỉnh và cạnh) có tổng trọng số lớn hơn hẳn độ dài đường đi ngắn nhất từ $1$ đến $N$ được gọi là hợp lệ cho vị trí thứ hai nếu nó là giá trị nhỏ nhất trong số các độ dài lớn hơn độ dài ngắn nhất. Hãy tìm độ dài đường đi ngắn thứ hai từ $1$ đến $N$ (nếu không tồn tại, in ra -1).
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N$ và $M$ ($1 \le N \le 10^5$, $0 \le M \le 2 \times 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$, $1 \le w \le 10^5$).
Dữ liệu ra
- In ra độ dài đường đi ngắn thứ hai (lớn hơn hẳn độ dài ngắn nhất) từ $1$ đến $N$, hoặc
-1nếu không tồn tại.
Ví dụ
| Input | Output |
|---|---|
| 4 4\n1 2 100\n2 4 200\n2 3 250\n3 4 100 | 450 |
| 2 1\n1 2 5 | 15 |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le M \le 2 \times 10^5$
- $1 \le w \le 10^5$
Community Discussion