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 JS NODEJS PERL 6 PYPY rust SED VB.net

hide comments
2016-08-03 04:45:27
có cách nào down test được k các bạn
2016-04-16 10:40:29
My code:
http://adf.ly/1ZUiLP
2016-04-13 03:55:51
Hướng dẫn chuẩn:
http://adf.ly/1ZNSiU
2016-03-26 11:10:13
Ngu người vậy ~~
1 Đấm Chẳng AC
2016-02-28 09:18:06
hên quá, nộp 1 lần AC
mấy cái bài loại này để Kết quả sai là đạp mấy, mò mệt lắm mới dc @@@
2015-12-26 09:58:44 The Flash
testcase sai từa lưa
có 1 test còn ghi đáp án là 2 1 1
đường đi có 2 đỉnh là 1 và 1 :v
2015-10-04 17:51:02 Bùi Tuấn Ðại
Cho mình hỏi:
trong test floyd.in0 lúc mình down về, thấy đáp án cho câu hỏi 1 3 3 là 2 3 3, nhưng mình ko thấy cạnh vòng từ 3->3. Vậy testcase bị sai à?
2015-10-03 10:31:59
Floyd cơ bản: Đạt yêu cầu: http://freepascal.chforum.net/t83-topic#90
2015-09-10 14:14:58
THAM KHẢO TẠI https://traitaodo.wordpress.com/2015/09/10/floyd-hoac-dijkstra-co-ban-floyd-2/

Last edit: 2015-10-02 03:23:30
2015-09-08 14:19:24
https://thewizard6296.wordpress.com/2015/09/04/5/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.