Tin học Việt

A place for learning and sharing knowledge


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

    Share

    Admin
    Admin
    Admin

    Posts : 48
    Golds : 2147483647
    Liked : 16
    Ngày tham gia : 2011-08-25
    Tuổi : 20
    Đến từ : Ho Chi Minh City

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

    Post by Admin on 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ụ:






    TANGQUA.INP

    TANGQUA.OUT

    9 7 5 1 4

    5 1 7

    6 7 2

    4 7 2

    5 6 1

    5 2 4

    4 3 2

    1 2 3

    3 2 2

    2 6 3

    12






    Last edited by Admin on Thu Mar 29, 2012 3:56 pm; edited 2 times in total

    fanchelseavip
    Mod
    Mod

    Posts : 2
    Golds : 2
    Liked : 0
    Ngày tham gia : 2012-02-11

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

    Post by fanchelseavip on Tue Mar 13, 2012 9:26 pm

    sao file inp bài gửi thư kỳ vậy ...
    p/s: lâu lắm r mới vào lại 4rum

    Admin
    Admin
    Admin

    Posts : 48
    Golds : 2147483647
    Liked : 16
    Ngày tham gia : 2011-08-25
    Tuổi : 20
    Đến từ : Ho Chi Minh City

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

    Post by Admin on Thu Mar 29, 2012 3:54 pm

    fanchelseavip wrote:sao file inp bài gửi thư kỳ vậy ...
    p/s: lâu lắm r mới vào lại 4rum

    Mình đã sửa lại rồi đó bạn !! Lúc soạn quên xem lại [You must be registered and logged in to see this image.]

    ptcgiang74

    Posts : 1
    Golds : 1
    Liked : 0
    Ngày tham gia : 2013-04-19

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

    Post by ptcgiang74 on Sun Apr 21, 2013 8:26 am

    cho minh loi giai cac bai tap do di nha!

    sonlv1112

    Posts : 1
    Golds : 1
    Liked : 0
    Ngày tham gia : 2014-02-07

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

    Post by sonlv1112 on Fri Feb 07, 2014 9:37 pm

    ai có lời giải up lên cho anh em tham khảo với. xin cảm ơn!

    Sponsored content

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

    Post by Sponsored content Today at 3:38 am


      Current date/time is Tue Dec 06, 2016 3:38 am