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.

Từ tập các bài có trên SPOJ (acm)

1301. Floyd hoặc Dijkstra ( Cơ bản )

Mã bài: FLOYD

Advertisement blocking software were detected ;( Please add this webpage to whitelist.

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 Pentium G860 3GHz)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL JAVA JS NODEJS PERL 6 PYPY rust SED VB.net

hide comments
2015-07-09 03:24:51 Hải
bị exit code 201
2015-07-04 03:08:56 Bee
Floyd cho gọn
2015-06-20 18:33:10 ptt
duyệt trâu cũng ac
2014-11-14 15:11:30 livw
3 1 2 3 co nghia la co 3 dinh tren duong di ngan nhat la 1, 2, 3
2014-11-03 16:09:46 juju
test đầu bài sai
3
4 1 2 3

ddnn từ đỉnh 1->3 phải là 4
2014-07-02 20:31:36 Thcs Ðặng Chánh Kỷ
Pom pon ba bạn downtest về chạy thử xem rồi hãy nạp chú ý từ i-->i ấy, đừng sub kiểu đó
2014-06-25 11:59:38 Kraken


Last edit: 2014-06-25 12:21:20
2014-05-05 14:29:09 Lưu Tiểu Tiểu
dijkstra bình thường cũng thừa kịp time mà đâu cần phải heap
2014-05-01 09:23:48  
từ (u,u) nếu là truy vấn 1 xuất 0 truy vấn 2 xuất 2 u u Nếu (u,v) không có đường đi, truy vấn 1 xuất -1
2014-04-16 15:08:47 Thcs Ðặng Chánh Kỷ
Ac_@: Cơ bản
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.