ĐƯỜ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