[Bài tập] Bài tập về đường đi ngắn nhất

by **Admin** Sun Mar 04, 2012 9:33 pm

Admin: Admin; Posts : 48
Golds : 2147483646
Liked : 18
Ngày tham gia : 2011-08-25
Tuổi : 27
Đến từ : Ho Chi Minh City

Post n°1

[Bài tập] Bài tập về đường đi ngắn nhất

by Admin Sun Mar 04, 2012 9:33 pm

GỬI THƯ

Một công ty bưu điện chịu trách nhiệm chuyển phát thư một cách nhanh chóng giữa các thành phố. Có tất cả N thành phố được đánh số từ 1..N, với M con đường hai chiều nối giữa các thành phố. Việc di chuyển trên mỗi con đường mất một khoảng thời gian là T. Bức thư từ thành phố A muốn gửi đến thành phố B phải đi theo một quy trình do công ty đặt ra. Đầu tiên nhân viên bưu điện mất một khoảng thời gian T1 vận chuyển thư từ thành phố A đến công ty bưu điện đặt tại thành phố 1 để kiểm tra tính hợp lệ của các bức thư, sau đó mất thêm một khoảng thời gian T2 để đưa các bức thư từ công ty đến thành phố B. Như vậy thời gian tổng cộng để gửi 1 bức thư từ thành phố A đến thành phố B là T1 T2.

Yêu cầu:
Biết rằng có rất nhiều yêu cầu gửi thư giữa các thành phố khác nhau.
Hãy tính thời gian ngắn nhất để một bức thư được gửi từ thành phố này đến thành phố khác.

Dữ liệu: Cho trong file văn bản GUITHU.INP

Dòng đầu tiên gồm 3 số nguyên N (2*K≤ N ≤50000), M (N-1 ≤ M ≤ 100000) và K (1≤ K ≤25000) cho biết số lượng thành phố, số con đường hai chiều, và số yêu cầu gửi thư giữa các thành phố.

M dòng tiếp theo, mỗi dòng ghi 3 số nguyên dương L, P, T (1≤L≠P≤N, 1≤T≤ 2000) biểu diễn cho việc di chuyển trên con đường hai chiều nối thành phố L và P, sẽ mất khoảng thời gian là T.

K dòng tiếp theo, mỗi dòng gồm 2 số nguyên A, B biểu diễn cho yêu cầu gửi thư từ thành phố A đến thành phố B.

Kết quả: Ghi ra file văn bản GUITHU.OUT gồm K dòng tương ứng với K yêu cầu gửi thư trong input, mỗi dòng gồm một số nguyên duy nhất biểu diễn thời gian ngắn nhất gửi một bức thư từ thành phố này đến thành phố khác.

Ví dụ:

GUITHU.INP	GUITHU.OUT
6 7 3 1 2 3 5 4 3 3 1 1 6 1 9 3 4 2 1 4 4 3 2 2 2 4 5 1 3 6	6 6 10

LẮP ĐIỆN

Công ty điện lực A xây dựng mạng lưới cung cấp điện gồm N cột điện đánh số từ 1 đến N, có tối đa 1 đường dây điện nối trực tiếp giữa hai cột điện bất kì. Vị trí của mỗi cột điện xác định thông qua hai sô thực X và Y trên mặt phẳng tọa độ. Tuy nhiên một trận mưa giông kéo theo nhiều sấm sét đã phá hủy nhiều đường dây điện.

Yêu cầu: Với các đoạn dây điện còn lại sau cơn giông, công
ty muốn truyền tải điện từ cột điện 1 đến cột điện N, hãy cho biết tổng chiều dài ngắn nhất của các đường dây điện cần lắp thêm. Biết rằng không có đường dây điện nào dài hơn một số thực K.

Dữ liệu: Cho trong file văn bản LAPDIEN.INP

Dòng đầu tiên gồm 2 số nguyên N, M (2 ≤ N ≤ 1000, 1 ≤ M ≤ 10000) biểu diễn số cột điện, số đường dây điện
Dòng thứ hai gồm 1 số thực K (0.0 < K <= 200,000.0)
N dòng tiếp theo, mỗi dòng gồm 2 số nguyên X,Y (-100000 ≤ X,Y ≤ 100000) biểu diễn tọa độ của một cột điện.
M dòng tiếp theo, mỗi dòng gồm 2 số nguyên A,B cho biết có đường dây điện nối trực tiếp hai cột điện A và B

Kết quả: Ghi ra file văn bản LAPDIEN.OUT gồm 1 số nguyên duy nhất,nếu không thể nối dây điện, xuất ra giá trị -1. Ngược lại, lấy tổng chiều dàicần lắp đặt thêm nhân với 1000, sau đó các số bỏ đi phần phía sau dấu thập phân(không làm tròn), ta sẽ được 1 số nguyên cần tìm.

Ví dụ:

LAPDIEN.INP	LAPDIEN.OUT
9 3 2.0 0 0 0 1 1 1 2 1 2 2 3 2 3 3 4 1 4 3 1 2 2 3 3 4	2828

TIỆC TẤT NIÊN

Công ty Yamaha quyết định tổ chức tiệc tất niên tại đại lý X để đánh dấu những thành công của hệ thống đại lý trong năm vừa qua. Mỗi đại lý của công ty được yêu cầu cử 1 nhân viên tham gia sự kiện. Hệ thống đại lý của công ty Yamaha gồm N đại lý được đánh số 1..N, và M con đường hai chiều nối các đại lý với nhau. Việc di chuyển trên con đường nối giữa hai đại lý mất một khoảng thời gian là T. Một hoặc nhiều cặp đại lý có thể trực tiếp kết nối bởi nhiều hơn một con đường.

Sau khi tất cả các nhân viên tập trung tại đại lý X, người ta nhận ra rằng đã quên yêu cầu các nhân viên phải đem theo bảng thống kê doanh thu của đại lý nhân viên đó đang làm. Vì vậy bữa tiệc tạm hoãn để yêu cầu các nhân viên quay trở về đại lý của mình lấy bảng thống kê, sau đó những nhân viên này sẽ quay lại bữa tiệc. Bữa tiệc chỉ được tổ chức lại khi tất cả nhân viên quay trở lại bữa tiệc. Để không trễ bữa tiệc, các nhân viên luôn chọn hành trình trở về đại lý và quay trở lại bữa tiệc sao cho thời gian di chuyển là ít nhất.

Yêu cầu:
Hãy cho biết bữa tiệc bị hoãn lại bao lâu.

Dữ liệu: Cho trong file văn bản TATNIEN.INP

·
Dòng đầu tiên gồm 3 số nguyên N (1 ≤ N ≤1000), M (1 ≤ M ≤ 100000) và X (1 ≤ X ≤ N) biểu diễn số lượng đại lý, số con đường và đại lý được chọn tổ chức buổi tiệc.

·
M dòng tiếp theo, mỗi dòng ghi 3 số nguyên dương A, B, T
( A≠B, 1 ≤ T ≤ 100) biểu diễn cho việc di chuyển trên con đường hai chiều nối đại lý A và B, sẽ mất khoảng thời gian là T.

Kết quả: Ghi ra file văn bản
TATNIEN.OUT gồm 1 dòng duy nhất cho biết thời gian bữa tiệc bị hoãn lại.

Ví dụ:

TATNIEN.INP	TATNIEN.OUT
4 8 2 1 2 7 1 3 8 1 4 4 2 1 3 2 3 1 3 1 2 3 4 6 4 2 2	6

Giải thích Input và Output

Từ đại lý 2 có đường đi hai chiều trực tiếp đến các đại lý tương ứng:
Đến đại lý 1: có 2 con đường với thời gian di chuyển lần lượt là 7 và 3
Đến đại lý 3: có 1 con đường với thời gian di chuyển là 1
Đến đại lý 4: có 1 con đường với thời gian di chuyển là 2
Thời gian bữa tiệc bị hoãn lại là 6.

TẶNG QUÀ

Sau khi tặng quà cho vô số các em thiếu nhi, trong túi của ông già Noel vẫn còn lại 2 món quà. Trời đã gần sáng, vì vậy ông già Noel quyết định sẽ đi tặng quà cho hai em còn lại với hành trình ngắn nhất. Tuy nhiên do phải làm việc cả đêm nên ông già Noel khát nước. Ông quyết định sẽ đến một ngôi nhà A nào đó trước để uống nước, sau đó sẽ tặng quà cho hai em ở hai ngôi nhà B và C.

Có tất cả N ngôi nhà đánh số 1..N và M con đường hai chiều nối những căn nhà với nhau. Mỗi con đường có một chiều dài (khoảng cách) là L.

Yêu cầu:
Hãy xác định khoảng cách ngắn nhất ông già Noel phải đi để có thể tặng quà cho hai em thiếu nhi.

Dữ liệu: Cho trong file văn bản TANGQUA.INP

·
Dòng đầu tiên gồm 5 số nguyên M (1 ≤ M ≤ 200000), N (1 ≤ N ≤100000), A, B, C (1 ≤ A, B, C ≤ N) biểu diễn lần lượt số con đường hai chiều, số ngôi nhà, ngôi nhà ông già Noel chọn uống nước và hai ngôi nhà tặng quà.

·
M dòng tiếp theo, mỗi dòng ghi 3 số nguyên dương P, Q, L ( P≠Q) biểu diễn con đường hai chiều nối 2 ngôi nhà P và Q sẽ có khoảng cách là L. Tổng khoảng cách của M con đường không vượt quá 2000000000

Kết quả: Ghi ra file văn bản
TANGQUA.OUT gồm 1 dòng duy nhất cho biết khoảng cách ngắn nhất.

Ví dụ: