Đường đi ngắn nhì
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho đồ thị vô hướng liên thông gồm $N$ đỉnh và $M$ cạnh có trọng số dương. Đường đi có thể đi qua lại một đỉnh hoặc một cạnh nhiều lần.
Hãy tìm độ dài của đường đi ngắn thứ nhì (strictly greater than the shortest path) từ đỉnh $1$ đến đỉnh $N$. Nếu không tồn tại (chỉ có tối đa 1 giá trị độ dài đường đi khác nhau — điều này chỉ xảy ra khi $M=0$ với $N=1$), in ra -1.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, M$ ($2 \le N \le 5 \cdot 10^4, 1 \le M \le 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^9$).
Dữ liệu ra
- Một số nguyên duy nhất là độ dài đường đi ngắn nhì từ $1$ đến $N$.
Ví dụ
| Input | Output |
|---|---|
| 4 4 1 2 100 2 4 200 2 3 250 3 4 100 |
450 |
Giới hạn
- $2 \le N \le 5 \cdot 10^4, 1 \le M \le 10^5$
Community Discussion