Con Đường Ngắn Thứ Hai

Buổi 19 — Đường đi ngắn nhất
Points
18
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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 -1 nế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$
Draft saved