Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FLOYD - Floyd hoặc Dijkstra ( Cơ bản )

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 => 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 .

Download test và solution tại đây

Input

Dòng 1 : 3 số nguyên N , M , K . ( 1 ≤ N ≤ 100 , 1 ≤ M ≤ N*(N-1)/2 , 1 ≤ K ≤ 1000 )
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 ≤ c ≤ 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 -> 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 .

Example

Input:
3 3 2
1 2 3
2 3 1
1 3 5
0 1 2
1 1 3

Output:
3
3 1 2 3

Được gửi lên bởi:Nguyen Minh Hieu
Ngày:2007-02-13
Thời gian chạy:0.163s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2013-05-10 09:09:27 Bitagi97
ờ răng lại Dijkstra nhỉ bài này Ployd mới AC chơ ???
2013-04-22 17:52:12 namlunoy
May mà có comment của anh đức không cũng ngất! :(
2013-04-05 14:37:28 MINH DUC
Mình dùng cái Floyd trong sách của thầy LMH mà sao KQ bị báo sai hoài à :(
2013-01-01 17:13:47 Nguyễn Thái Cường
Tập viết HEAP :D
2013-01-01 14:51:40 Nguyễn Thái Cường
Bạn chú ý tí là sửa đc thôi, ko sai đâu
2012-12-19 02:05:26 Khủng Long Lùn
Ủa lỗi sigkill là lỗi gì vậy mọi người? Mình nộp mấy lần mà vẫn bị báo lỗi đó :(
2012-11-21 12:45:17 Stupider
u=v thì in ra là phải đi qua 2 đỉnh
chỉ vì thế mà mất 1 tuần của đời ta T^T
2012-11-06 06:07:16 Một Bạn Trai Giấu Tên
hình như mấy bộ answer sai thì phải. mình vẽ cả đồ thị ra kiểm tra = tay. ngay test đầu tiên, 9 4 không có đường mà trong answer nói 8 -> 4 là 8 9 4
2012-07-22 13:45:03 Hải Phong
đi từ i->i sẽ viết là 2 i i chứ ko phải 1 i như out của m nên kết quả toàn sai
2012-07-18 09:53:10 wd
làm mãi mà vẫn sai kết quả @@
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.