Đường Đi Tải Trọng Nhỏ Nhất

Buổi 19 — Đường đi ngắn nhất
Points
30
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ố gồm $N$ đỉnh và $M$ cạnh. Hãy tìm một đường đi từ đỉnh $1$ đến đỉnh $N$ sao cho trọng số lớn nhất của một cạnh bất kỳ trên đường đi đó là nhỏ nhất có thể. In ra giá trị trọng số lớn nhất nhỏ nhất đó (nếu $N = 1$, in ra 0; nếu không có đường đ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$, $0 \le w \le 10^9$).
Dữ liệu ra
  • In ra giá trị cần tìm, hoặc -1 nếu không có đường đi từ $1$ đến $N$.
Ví dụ
Input Output
4 4\n1 2 5\n2 4 3\n1 3 4\n3 4 4 4
3 1\n1 2 10 -1
Giới hạn
  • $1 \le N \le 10^5$
  • $0 \le M \le 2 \times 10^5$
  • $0 \le w \le 10^9$
Draft saved