Cho đơ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.
Comments
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 @@?