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:1s
Giới hạn mã nguồn:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL JS NODEJS PERL 6

hide comments
2014-07-02 20:31:36 [FPT]
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 Nguyễn Ngọc Quang
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 [FPT]
Ac_@: Cơ bản
2014-04-16 14:34:28 [FPT]
từ i-->i in ra 0 hay in ra i hầy
2014-04-13 07:52:35 Dynamite
sai ngay test 9
2014-03-30 05:32:01 Phạm Nhật Trường
ai c cng thức truy vết thuật ton dijkstra cho m vs ( cylasion@gmail.com )
2014-03-12 20:20:12 Chu Minh Hiếu


Last edit: 2014-06-24 04:05:47
2014-02-13 15:14:21 Kha Kha Kha


Last edit: 2014-02-13 15:14:50
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.