Olympic 30/4 2016 - Khối 10 - Bài 2 - Tải trọng tuyến đường

Điểm: 0,40 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: TAITRONG.INP

Output: TAITRONG.OUT

Nguồn bài:

Olympic 30/4

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một hệ thống giao thông gồm ~n~ thành phố được đánh số từ ~1~ đến ~n~. Hệ thống giao thông có ~m~ đoạn đường hai chiều nối giữa các thành phố (giữa hai thành phố bất kỳ luôn có đường đi). Mỗi đoạn đường có một tải trọng tối đa là ~z~, cho biết các xe với tải trọng không lớn hơn ~z~ mới lưu thông được trên con đường đó.

Yêu cầu: Cho trước tải trọng của các đoạn đường trong hệ thống giao thông. Hãy tìm một hành trình từ thành phố ~s~ đến thành phố ~t~ sao cho tải trọng cho phép của xe lưu thông trên hành trình đó là lớn nhất có thể.

Input

Cho từ tệp văn bản TAITRONG.INP gồm:

Dòng thứ nhất ghi ~4~ số nguyên ~n,\ m,\ s,\ t~ ~(2\le n \le 10^3;\ 1\le m \le 10^4;\ 1\le s,\ t\le n; s\ne t)~.
Tiếp theo là ~m~ dòng, mỗi dòng ghi ~3~ số nguyên ~x,\ y,\ z~ với ý nghĩa có đoạn đường giữa thành phố ~x~ và thành phố ~y~ với tải trọng tối đa cho phép là ~z~ ~(1 \le z \le 10^4)~.

Các số trên cùng dòng viết cách nhau bởi ít nhất một dấu cách.

Output

Ghi vào tệp văn bản TAITRONG.OUT gồm một dòng ghi số nguyên là tải trọng lớn nhất cần tìm.

Scoring

~50\%~ số test tương ứng với ~50\%~ số điểm của bài có ~2\le n \le 100~.

Sample Input 1

Sample Output 1

Bình luận

Hãy đọc nội quy trước khi bình luận.

0
minhkochamhoc đã bình luận lúc 16, Tháng 6, 2025, 9:18 ← chỉnh sửa →
solve :

giải thích đề:

trước hết dựa vào đề ta cần hiểu tải trọng cho phép của 1 con đường khi đi từ s -> t là giá trị tải nhỏ nhất nằm trên đoạn đường đi đó ( gọi giá trị này là x) vì nếu ta để 1 xe có tải trọng lớn hơn x đi qua con đường đó thì chắc chắn ta ko để đi từ s -> t theo đoạn đường đó được ( ví dụ nếu tải trọng nhỏ nhất là 2 mà có xe có tải trọng 5 đi qua thì ko thể dù giả sử các con đường khác có tải trọng lớn hơn 5 ta cx ko thể nào đi được vì ngay ở đoạn có tải trọng 2 đã ko đi tiếp đc rồi )

do đó nhìn lại ví dụ đề bài ta sẽ có các lựa chọn là từ 1->2->4 và có tải trọng cho phép là 1 , từ 1->3->4 có tải trọng cho phép là 3 , từ 1->4 có tải trọng cho phép là 2 . dễ thấy lựa chọn mang lại tải trọng cho phép lớn nhất là 1->3->4 và đạt giá trị là 3 như ví dụ

từ đó ta hình dung bài tập trên rằng nếu có nhiều sự lựa chọn đường đi từ s->t ta lựa chọn đường đi nào đó sao cho TẢI TRỌNG NHỎ NHẤT CỦA ĐƯỜNG ĐI ĐÓ LÀ LỚN NHẤT (hay nói cách khác chọn đường đi sao cho tất cả tải trọng trên đường đi đó lớn nhất có thể)

ý tưởng giải :

ta sử dụng 2 ý tưởng chính là DSU xây MST và Dijkstra với mục tiêu đều là tìm xem đường đi nào có các cạnh trọng số lớn nhất như đã nói ở trên và kết quả là trọng số nhỏ nhất của đường đi đó.

code của mình bằng DSU : hehehe

-11

THPTHD_Hieu đã bình luận lúc 12, Tháng 5, 2025, 7:30

1 đấm ac ez vl

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-1

RussVN123 đã bình luận lúc 13, Tháng 5, 2025, 6:42

Gà chiến !

-4

THPTHD_Hieu đã bình luận lúc 13, Tháng 5, 2025, 8:11

Hiếu chiến !

-3

vendettas đã bình luận lúc 6, Tháng 4, 2025, 5:41

um nha anh trong mit thai

-2

phanmd đã bình luận lúc 6, Tháng 4, 2025, 8:46

Không kể thì im lặng

-18

gv_THCSgiaphu_Vuhuuphong đã bình luận lúc 19, Tháng 3, 2024, 8:35

Để giải bài toán này, chúng ta có thể sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhất từ thành phố xuất phát đến các thành phố khác. Tuy nhiên, thay vì tìm đường đi ngắn nhất, chúng ta sẽ tìm đường đi có tải trọng lớn nhất có thể.

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.