Elearning CodePath – CTP Online Judge

Cầu nối an toàn

GRAPH004

🟢 Easy #Graph #Binary Search #Combinatorics

### 📌 Thông tin chung

### Bài toán

Có n hòn đảo được đánh số từ 1 đến n và m cây cầu nối giữa chúng. Mỗi cây cầu nối giữa hai hòn đảo u và v có độ bền là w. Một phương tiện có trọng tải X chỉ có thể đi qua một cây cầu nếu độ bền của cầu đó lớn hơn hoặc bằng X.

Yêu cầu: Tìm giá trị X lớn nhất để phương tiện có thể di chuyển từ đảo s đến đảo t thông qua các cây cầu hiện có.

### Định dạng Đầu vào

Dữ liệu vào từ file BRIDGE.INP:
* Dòng đầu tiên chứa bốn số nguyên n, m, s, t lần lượt là số hòn đảo, số cây cầu, điểm xuất phát và điểm kết thúc.
* m dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, w mô tả một cây cầu nối đảo u và đảo v với độ bền w.

Giới hạn:
* 1 <= n <= 1000.
* 1 <= m <= 20000.
* 1 <= w <= 10^6.
* 1 <= s, t <= n.

### Định dạng Đầu ra

Ghi ra file BRIDGE.OUT một số nguyên duy nhất là giá trị X lớn nhất tìm được. Nếu không có đường đi từ s đến t, ghi -1.

### Ví dụ

| Input (BRIDGE.INP) | Output (BRIDGE.OUT) |
| :--- | :--- |
| 5 6 1 5 1 2 5 2 3 4 3 5 6 1 4 3 4 5 2 2 5 1 | 4 |

Giải thích:
Đường đi 1 -> 2 -> 3 -> 5 có các cạnh lần lượt là 5, 4, 6. Độ bền nhỏ nhất trên đường này là 4. Đây là giá trị lớn nhất có thể đạt được.

### Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | n <= 100, m <= 500 | 40% |
| 2 | n <= 1000, m <= 20000 | 60% |

✅ Đã AC: 0 / 0 submissions