Bài tập đường đi ngắn nhất

Cho N hình tròn (đánh số từ 1 đến N). Một người muốn đi từ hình tròn này sang hình tròn khác cần tuân theo qui ước:

- Nếu khoảng cách giữa 2 điểm gần nhất của 2 hình tròn không quá 50 cm thì có thể bước sang.

- Nếu khoảng cách này hơn 50cm và không quá 80cm thì có thể nhảy sang.

- Các trường hợp khác không thể sang được.

Một đường đi từ hình tròn này sang hình tròn khác đuợc gọi là càng "tốt" nếu số lần phải nhảy là càng ít. Hai đường đi có số lần nhảy bằng nhau thì đường đi nào có số hình tròn đi qua ít hơn thì đường đi đó "tốt" hơn.

Các hình tròn được cho trong một file văn bản, trong đó dòng thứ i mô tả hình tròn số hiệu i (i = 1, 2,..., N) bao gồm 3 số thực: hoành độ tâm, tung độ tâm, độ lớn bán kính (đơn vị đo bằng mét).

Lập trình đọc các hình tròn từ một file văn bản (tên file vào từ bàn phím), sau đó cứ mỗi lần đọc số hiệu hình tròn xuất phát S và hình tròn kết thúc T từ bàn phím, chương trình sẽ đưa ra đường đi từ S đến T là "tốt nhất" theo nghĩa đã nêu (hoặc thông báo là không có).

Yêu cầu đường đi được viết dưới dạng một dãy các số hiệu hình tròn lần lượt cần được đi qua trong đó nói rõ tổng số các bước nhảy, tổng số các hình tròn đi qua và những bước nào cần phải nhảy.

Giới hạn số hình tròn không quá 100.

Trên một mạng lưới giao thông, một người muốn đi từ điểm A đến điểm B bằng xe máy. Xe chứa được tối đa 3 lít xăng và chạy 100km hết 2,5 lít. Các trạm xăng chỉ được đặt ở các điểm dân cư, không đặt ở giữa đường và người này không mang theo bất kỳ thùng chứa xăng nào khác. Hãy viết chương trình nhập vào mạng lưới giao thông và xác định giúp người này tuyến đường đi từ A đến B sao cho ít tốn xăng nhất.

Trên một đảo quốc, có N hòn đảo. Giả sử tất cả các đảo đều có hình dạng là hình chữ nhật nằm ngang. Trên mỗi hòn đảo có thể có sân bay nằm ở trung tâm đảo, có thể có cảng nằm ở 4 góc đảo. Trên mỗi đảo đều có tuyến đường xe buýt nối 4 góc đảo với nhau và với trung tâm đảo. Giữa 2 đảo có thể đi lại bằng máy bay nếu cả 2 đảo đều có sân bay và có thể đi lại bằng tàu nếu cả 2 đảo đều có cảng.

Giả sử rằng:

- Các tuyến đường (bộ, không, thủy) đều là đường thẳng.

- Chi phí cho mỗi km và tốc độ của mỗi loại phương tiện là:

Hãy viết chương trình xác định tuyến đường và cách di chuyển giữa 2 hòn đảo trong đảo quốc sao cho:

- Thời gian di chuyển ít nhất.

- Chi phí di chuyển ít nhất.

- Thời gian di chuyển ít nhất nhưng với một số tiền chi phí không quá Đ đồng.

- Chi phí di chuyển ít nhất nhưng với thời gian di chuyển không vượt quá T giờ.

Các ô tô đi từ các thành phố khác nhau x₁, x₂,…., x_n và cùng tới một địa điểm thống nhất y. Nếu tồn tại đường đi từ x_i đến x_j thì ta ký hiệu t_ij là thời gian cần thiết để đi từ x_i đến x_j, c_ij là lượng ô tô có thể đi trên con đường đó trong một đơn vị thời gian (c_ij = 0 nếu không có đường đi), c_ii là lượng ô tô có thể nghỉ đồng thời ở thành phố x_i, a_i là số lượng xe ban đầu có ở x_i. Hãy tổ chức hành trình sao cho trong khoảng thời gian t số ô tô tới y là nhiều nhất.

Giả sử X là tập các khu dân cư, U là tập các đường sá nối liền các khu đó. Ta giả sử mọi chỗ giao nhau của các con đường đều thuộc X. Với con đường u, số l(u) là độ dài của u tính bằng km. Hãy chỉ ra tuyến đường đi từ một khu i sang khu j sao cho tổng chiều dài là nhỏ nhất.

Cho 1 ma trận A[M, N], mỗi phần tử của nó chứa 1 số tự nhiên. Từ 1 ô (i, j) ta có thể đi sang ô kề nó (có chung 1 cạnh) nếu giá trị của ô kề này nhỏ hơn giá trị lưu trong (i, j). Hãy tìm 1 đường đi từ ô (i, j) tới ô (k, l) trên ma trận sao cho phải đi qua ít ô nhất. Hãy tìm 1 đường đi từ ô (i, j) tới ô (k, l) trên ma trận sao cho tổng giá trị các ô phải đi qua nhỏ nhất.

Có N thành phố được đánh số từ 1..N nối với nhau bằng các đoạn đường một chiều. Mỗi đoạn đường bao gồm 2 thông số : Độ dài và chi phí đi của đoạn đường.

A sống tại thành phố 1 và A muốn di chuyển đến thành phố N nhanh nhất có thể.

Bạn hãy giúp A tìm ra đường đi ngắn nhất từ thành phố 1 đến thành phố N mà A có khả năng chi trả tiền.Dữ liệu vào: ROADS.IN

- Dòng đầu tiên chứa số nguyên K, 0 <= K <= 10000, số tiền mà A có.

- Dòng thứ 2 chứa số nguyên N, 2 <= N <= 100, số thành phố.

- Dòng thứ 3 chứa số nguyên R, 1 <= R <= 10000, tổng số đoạn đường.

- Mỗi dòng trong số R dòng tiếp theo mô tả một đoạn đường bằng các số S, D, L và T cách nhau bởi ít nhất một khoảng trắng.

+ S là thành phố khởi hành, 1 <= S <= N.

+ D là thành phố đến, 1 <= D <= N.

+ L là độ dài của đoạn đường, 1 <= L <= 100.

+ T là lộ phí, 0 <= T <= 100.

Chú ý rằng giữa 2 thành phố có thể có nhiều đoạn đường nối 2 thành phố này.

Dữ liệu ra: ROADS.OUT

Chỉ có duy nhất 1 dòng chứa tổng độ dài của đường đi ngắn nhất từ 1->N và nhỏ hơn K.