SPOJ.com - Problem FLOYD

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

Submit solution!

Đượ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:	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

2019-04-10 05:40:29
TEST *** LÀ CÓ THẬT 1 1 1 = > 2 1 1
if (s==f){
printf("2 %d %d", s, f);
}
= >> AC

2018-10-01 20:23:03
chạy cin cout bt 1 đấm ac hjhj =))

2018-05-30 16:13:40
xài cin, cout quá thời gian -> xài scanf, printf AC

2018-01-05 04:35:21

Last edit: 2018-01-05 04:36:06

2017-11-07 01:42:27

Last edit: 2017-11-07 01:42:39

2017-10-04 10:03:53
Code AC: http://123link.top/FLOYD

2017-08-19 09:01:44 Con Bò Huyền Thoại
https://kienthuc24h.com/floyd-spoj-floyd-hoac-dijkstra-co-ban/

2017-07-19 04:47:38
Lai trau AC =))

2017-06-20 13:49:33
1 đấm = dijkstra đệ quy AC :D Tùng béo tuổi tôm :D

Last edit: 2017-06-20 13:49:57

2017-06-20 11:56:45
Mong tác giả xem lại testcase. Trong output có một output là 2 3 3 mà lại không tồn tại đường đi từ 3 đến chính nó. Có lẽ trong code sinh test quên xét trường hợp truy vấn đường đi với 2 đỉnh đầu cuối trùng nhau :)

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

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

Input

Output

Example