Floyd hoặc Dijkstra (Cơ bản)
Xem dạng PDFCho đơn đồ thị vô hướng ~N~ đỉnh và ~M~ cạnh, trọng số các cạnh đều nguyên dương. Có ~2~ loại câu hỏi:
~0~ ~u~ ~v~: Cho biết đường đi ngắn nhất từ ~u~ tới ~v~ có độ dài là bao nhiêu.
~1~ ~u~ ~v~: Hãy chỉ ra ~1~ đường đi ngắn nhất từ ~u \rightarrow v~
Bài cơ bản này nhằm kiểm tra kỹ năng xây dựng các module chương trình con dành cho truy vết ~1~ cách hợp lý, sử dụng nhuần nhuyễn chương trình con, lời gọi hàm.
Input
Dòng ~1~: ~3~ số nguyên ~N~, ~M~, ~K~. ~\left(1 \leq N \leq 100, 1 \leq M \leq \frac{N(N-1)}{2}, 1 \leq K \leq 1000\right)~
~M~ dòng tiếp theo, dòng thứ ~i~ gồm ~3~ số nguyên dương ~u~, ~v~, ~c~ cho biết cạnh (~u~, ~v~) có trọng số là ~c~ ~(1 \leq c \leq 10000)~
~K~ dòng tiếp theo là ~K~ câu hỏi, dòng thứ ~j~ sẽ có định dạng như đã nêu ở trên.
Output
Ứng với mỗi câu hỏi trong ~K~ câu hỏi thì ta phải trả lời trên mỗi dòng như sau.
Câu hỏi ~0~ ~u~ ~v~: Ghi ra ~1~ số nguyên duy nhất là độ dài đường đi ngắn nhất từ ~u \rightarrow v~.
Câu hỏi ~1~ ~u~ ~v~: Ghi ra số đầu tiên là số ~X~ là số đỉnh trên đường đi ngắn nhất này, tiếp đó ghi ra ~X~ số là chỉ số các đỉnh theo thứ tự xuất hiện trên hành trình.
Sample Input
3 3 2
1 2 3
2 3 1
1 3 5
0 1 2
1 1 3
Sample Output
3
3 1 2 3
Note
Download test và solution tại đây.
Lưu ý: Do thay đổi về trình chấm (trình chấm mới không chấp nhận 1 đỉnh tự quay lại chính nó nếu không có cạnh ở input), do đó solution ở trên sẽ không AC ở VNOJ.
Bình luận
Mình có 2 thắc mắc xin nhờ mọi người giải đáp
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Trường hợp đó đường đi có một đỉnh là chính đỉnh đó nha bạn
Ad ơi sao e nộp fpc mà test 1 ra runtime error mà e dùng phiên bản fpc y thế cũng 3.2.2 thì chạy ra bth là ntn nhỉ, e dùng ideone và delphi để chạy thì nó cũng ra kq ok @@?
Lưu ý cái này ở trên nhé bạn: Do thay đổi về trình chấm (trình chấm mới không chấp nhận 1 đỉnh tự quay lại chính nó nếu không có cạnh ở input), do đó solution ở trên sẽ không AC ở VNOJ.
z output là gì khi vào trường hợp đó: -1 hay không in gì
mình cũng bị vậy
real?