Đường đi ngắn nhì

Buổi 71-72 — Ôn tập
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved