Đường Đi Tải Trọng Nhỏ Nhất
Points
30
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ố 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
-1nế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$
Community Discussion