[THHV 2019 - CLC - 11] Bài 3: ĐỒ THỊ
Xem dạng PDF
Gửi bài giải
Điểm:
10,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Người đăng:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Cho đồ thị ~n~ đỉnh và ~m~ cạnh. Đồ thị có thể có hướng hoặc không. Trọng số của mỗi cạnh là không âm. Hãy xác định đường đi ngắn nhất từ đỉnh ~s~ cho trước tới mỗi đỉnh còn lại và độ dài của đường đi đó.
Yêu cầu: Tìm đường đi ngắn nhất từ đỉnh ~s~ đến các đỉnh còn lại và truy vết đường đi cho các đỉnh yêu cầu.
Input
- Dòng đầu tiên chứa 2 số nguyên ~n~ và ~m~ (~n > 0, m \ge 0~)
- Nếu ~m > 0~ thì mỗi dòng trong ~m~ dòng tiếp theo chứa 3 số nguyên ~a, b, r~ cho biết có cạnh nối từ ~a~ tới ~b~ với trọng số ~r~ (~1 \le a, b \le n, a \ne b, 0 \le r \le 10^6~), không có hai dòng nào giống nhau.
- Dòng ~m+2~ chứa số nguyên ~s~ (~1 \le s \le n~).
- Dòng cuối cùng chứa số nguyên ~k~ và sau đó là ~k~ số nguyên ~c_1, c_2, \dots, c_k~ cho biết phải dẫn xuất đường đi ngắn nhất từ ~s~ tới ~c_i~, ~i=1 \dots k, 1 \le c_i \le n~.
Output
- Dòng đầu tiên chứa ~n~ số nguyên, số thứ ~i~ là độ dài đường đi ngắn nhất từ ~s~ đến đỉnh ~i~. Độ dài bằng -1 nếu không tồn tại đường đi từ ~s~ đến đỉnh đó.
- Dòng thứ ~i~ trong ~k~ dòng sau chứa thông tin về đường đi ngắn nhất (dạng: TU DINH s to ci: v1 v2 ... vk).
Sample Input 1
6 9
1 2 10
1 3 5
2 4 5
3 4 2
2 5 3
3 6 15
4 6 10
4 5 9
5 6 4
2
2 1 6
Sample Output 1
10 0 7 5 3 7
TU DINH 2 to 1: 2 1
TU DINH 2 to 6: 2 5 6
Bình luận
Test 3, 4 sai. Khả năng cao input truy vấn đường đi không tồn tại...
bạn này giỏi thật