Hành trình trọng tải nhỏ nhất
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh. Mỗi cạnh $(u, v)$ có độ nguy hiểm là $w$. Khi đi từ $1$ đến $N$ theo một đường đi, độ nguy hiểm của cả hành trình được tính là độ nguy hiểm lớn nhất trong các cạnh đi qua. Hãy tìm giá trị độ nguy hiểm nhỏ nhất có thể để đi từ $1$ đến $N$, hoặc -1 nếu không thể đến $N$.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, M$ ($1 \le N \le 10^5$, $0 \le M \le 2 \cdot 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
- Một số nguyên duy nhất là độ nguy hiểm nhỏ nhất có thể, hoặc
-1.
Ví dụ
| Input | Output |
|---|---|
| 4 5 1 2 5 2 4 10 1 3 3 3 4 7 2 3 4 |
7 |
| 3 1 1 2 5 |
-1 |
Giới hạn
- $1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$
- $0 \le w \le 10^9$
Community Discussion