Cho đơn đồ thị có hướng với N đỉnh (0 < N < 1000) có trọng số không âm. Hãy tìm đường đi ngắn nhất từ đỉnh u đến đỉnh v bất kỳ của đồ thị.

Yêu cầu: Sử dụng thuật toán Dijkstra hoặc Ford-Bellman để giải bài tập này.

Dữ liệu vào:

- Dòng 1: Nhập 3 số N u v

- N dòng tiếp theo: nhập ma trận trọng số của đồ thị

Dữ liệu ra:

-  Nếu có đường đi thì xuất:

+        Tổng độ dài đường đi

+        Đường đi từ v ngược về u theo mẫu: v<- ... <-u

-  Nếu không có đường đi xuất “NO”

Ví dụ:

Input:

6 1 6

0 1 0 0 0 0

0 0 5 2 0 7

0 0 0 0 0 1

2 0 1 0 4 0

0 0 0 3 0 0

0 0 0 0 1 0

Output:

5

6<-3<-4<-2<-1