ĐƯỜNG ĐI NGẮN NHẤT

(có thể dùng Floyd hoặc Dijkstra)

Cho đồ thị vô có hướng có N đỉnh, các đỉnh được đánh số từ 1 đến N. Đồ thị được biểu diễn bởi ma trận kề trong đó A[i,j] là trọng số của cung (i,j).

Có m truy vấn dạng (u_i ,v_i) với mỗi truy vấn cần đưa ra các thông tin:

+ Độ dài đường đi ngắn nhất từ u_i đến v_i

+ Đường đi ngắn nhất theo chiều từ u_i đến v_i

Dữ liệu vào: từ tệp DIJKSTRA.INP

+Dòng đầu tiên ghi số nguyên dương N

+ N dòng tiếp theo biểu diễn ma trận kề A, trong đó  A[i,j]=0 nếu không có cung (i,j), A[i,j]>0 nếu có cung (i,j).

+ Dòng tiếp theo là số nguyên dương m

+ m dòng tiếp theo mỗi dòng chứa 1 truy vấn (u_i ,v_i)

Dữ liệu ra: ghi vào tệp văn bản DIJKSTRA.OUT gồm m dòng

dòng thứ i gồm:

+ Số đầu tiên ghi -1 nếu không có đường đi từ u_i đến v_i ngược lại ghi độ dài đường đi ngắn nhất từ u_i đến v_i

+ Nếu số đầu tiên ghi một số nguyên dương thì các số tiếp theo ghi thứ tự các đỉnh của đường đi ngắn nhất từ u_i đến v_i.

Ví dụ:

DIJKSTRA.INP	DIJKSTRA.OUT
6 0 1 5 0 0 0 0 0 3 4 9 0 0 0 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 10 2 1 5 1 6	6 1 2 4 5 -1

Giới hạn:

+ 2<=N<=100

+ 0<=A_ij <= 100

TEST

TRAFFICN

Nguồn bài: http://vn.spoj.com/problems/TRAFFICN/

Mạng lưới giao thông thành phố gồm N nút được đánh số từ 1 đến N và m đường một chiều nối giữa các cặp nút. Để giảm được độ dài của đường đi ngắn nhất giữa hai nút trọng yếu s và t khác nhau, một danh sách gồm k đường hai chiều được đề xuất để xem xét xây dựng

Nhiệm vụ của bạn là chọn 1 đường hai chiều trong danh sách đề xuất trên để xây dựng sao cho độ dài đường đi giữa s và t là nhỏ nhất

Dữ liệu vào: từ file TRAFFICN.INP

+ Dòng đầu tiên  chứa 5 số nguyên dương: N (N≤1000), m , k (k≤300), s (1≤s≤N), t (1≤t≤N) cách nhau bởi dấu cách.

+ Dòng thứ i trong m dòng tiếp theo chứa 3 số nguyên dương di, ci, li cách nhau bở dấu cách, trong đó li là độ dài (0≤li≤1000) của đường một chiều thứ i từ nút di đến nút ci. Dòng thứ j trong k dòng tiếp theo chứa 3 số nguyên dương uj, vj và qj (qj≤1000) cách nhau bởi dấu cách, trong đó qj là độ dài đường đi hai chiều được đề xuất thứ j nối hai nút uj và vj.

Dữ liệu ra: ghi vào file TRAFFICN.OUT là một số nguyên duy nhất là độ dài nhỏ nhất có thể của đường đi ngắn nhất của hai nút trọng yếu sau khi xây dựng xong một đường hai chiều từ danh sách đề xuất. Trường hợp không có đường đi từ s đến t ghi -1

(Không nhất thiết phải có đường 2 chiều trong đường đi ngắn nhất)

TĂNG GIỚI HẠN CỦA N VÀ M KHI DÙNG DIJKSTRA HEAP

Ví dụ:

TRAFFICN.INP	TRAFFICN.OUT
4 5 3 1 4 1 2 13 2 3 19 3 1 25 3 4 17 4 1 18 1 3 23 2 3 5 2 4 25	35

TEST