Sat Sep 01, 2012 3:18 pm
Admin 1/ Cuộc hàng quân dã ngoại :
Một đoàn học sinh tổ chức hành quân dã ngoại , Có N địa điểm (2<=N<=100) và thời gian đi lại giữa hai địa điểm không vượt quá 100 , các địa điểm được đánh số từ 1 đến N .
Mỗi học sinh trong đoàn đều cũng xuất phát từ địa điểm 1 đi theo N con đường nào đó tới địa điểm N . Tại mỗi giao lộ , đoàn học sinh lại phải phân ra thành các nhóm , mỗi nhóm đi theo một tuyến đường rẽ nhánh .
Để đảm bảo an toàn . nếu nhóm đến một địa điểm nào đó sớm hơn thì nhóm đó phải chờ tất cả các nhóm khác đến đông đủ rồi mới phân nhóm con tiếp tục hành trình . Từ điiểm xuất phát luôn có có đường đi đến bất cứ địa điểm nào và từ một địa điểm bất kì luôn có đường đi đến địa điểm đích .
Yêu Cầu 1 : Tính thời điểm sớm nhất T khi nhóm cuối cùng về đến đích N .
Yêu Cầu 2 : Tính tổng thời gian chờ H khi đoàn học sinh đi từ địa điểm 1 đến địa điểm N .
Yêu Cầu 3 : Hãy xác định số lượng địa điểm mà tại đó các nhóm học sinh có thể nghỉ ngơi trước khi tiếp tục hành trình .
Dữ liệu vào : HIKE.INP
- Dòng 1 : Ghi 2 số N ( số địa điểm ) và M ( số con đường )
- M dòng tiếp theo , dòng thứ I trong m dòng ghi 3 số i , j , u là địa điểm đầu , địa điểm cuối , thời gian đi từ địa điểm đầu đến địa điểm cuối .
Dữ liệu ra : HIKE.OUT
- Dòng 1 : Ghi 3 số T,H, K( số lượng địa điểm nghỉ ngơi ) .
- Dòng 2 : Ghi K số là các địa điểm nghỉ ngơi
Một đoàn học sinh tổ chức hành quân dã ngoại , Có N địa điểm (2<=N<=100) và thời gian đi lại giữa hai địa điểm không vượt quá 100 , các địa điểm được đánh số từ 1 đến N .
Mỗi học sinh trong đoàn đều cũng xuất phát từ địa điểm 1 đi theo N con đường nào đó tới địa điểm N . Tại mỗi giao lộ , đoàn học sinh lại phải phân ra thành các nhóm , mỗi nhóm đi theo một tuyến đường rẽ nhánh .
Để đảm bảo an toàn . nếu nhóm đến một địa điểm nào đó sớm hơn thì nhóm đó phải chờ tất cả các nhóm khác đến đông đủ rồi mới phân nhóm con tiếp tục hành trình . Từ điiểm xuất phát luôn có có đường đi đến bất cứ địa điểm nào và từ một địa điểm bất kì luôn có đường đi đến địa điểm đích .
Yêu Cầu 1 : Tính thời điểm sớm nhất T khi nhóm cuối cùng về đến đích N .
Yêu Cầu 2 : Tính tổng thời gian chờ H khi đoàn học sinh đi từ địa điểm 1 đến địa điểm N .
Yêu Cầu 3 : Hãy xác định số lượng địa điểm mà tại đó các nhóm học sinh có thể nghỉ ngơi trước khi tiếp tục hành trình .
Dữ liệu vào : HIKE.INP
- Dòng 1 : Ghi 2 số N ( số địa điểm ) và M ( số con đường )
- M dòng tiếp theo , dòng thứ I trong m dòng ghi 3 số i , j , u là địa điểm đầu , địa điểm cuối , thời gian đi từ địa điểm đầu đến địa điểm cuối .
Dữ liệu ra : HIKE.OUT
- Dòng 1 : Ghi 3 số T,H, K( số lượng địa điểm nghỉ ngơi ) .
- Dòng 2 : Ghi K số là các địa điểm nghỉ ngơi
- Code:
HIKE.INP
8 12
3 7 12
5 2 5
6 3 7
1 6 6
4 7 10
2 9 11
1 5 5
5 3 4
6 4 5
7 8 9
4 3 3
3 2 9
HIKE .OUT
35 24 2
2 5