Giải bài trực tuyến

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

Cho ơn ồ thị v hướng N ỉnh và M cạnh, trọng số cc cạnh ều nguyên dương. C 2 loại cu 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ỹ nng xy dựng cc module chương trình con dành cho truy vết 1 cch 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 cu hỏi , dòng thứ j sẽ c ịnh dạng như ã nêu ở trên .

Output

Ứng với mỗi cu hỏi trong K cu hỏi thì ta phải trả lời trên mỗi dòng như sau .
Cu 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.
Cu 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ố cc ỉ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 JS NODEJS PERL 6

hide comments
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 0169.961.98xx
test ầu bài sai
3
4 1 2 3

ddnn từ ỉnh 1->3 phải là 4
2014-10-07 07:19:55 Con Bò Huyền Thoại
cho mình hỏi mấy bạn 0.0s là write test lun à :)) =))
2014-07-02 20:31:36 Mỹ Duyên (Genius Of The Effort)
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) khng c ường i, truy vấn 1 xuất -1
2014-04-16 15:08:47 Mỹ Duyên (Genius Of The Effort)
Ac_@: Cơ bản
2014-04-16 14:34:28 Mỹ Duyên (Genius Of The Effort)
từ i-->i in ra 0 hay in ra i hầy
2014-04-13 07:52:35 Dynamite
sai ngay test 9
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.