Dữ liệu vào
- Cho nhiều bộ test. Mỗi bộ test sẽ bắt đầu là một dòng chứa
số nguyên không âm . Trong đó là số đỉnh được đánh số từ đế , là số cạnh, là số lượng câu truy vấn, là đỉnh bắt đầu. Tiếp theo là dòng, mỗi dòng chứa số nguyên là cạnh nối đỉnh đến có trọng số là . Theo sau là dòng, mỗi dòng chứa một số nguyên không âm, hỏi khoảng cách nhất nhất từ đến đỉnh đó. - Nếu dữ liệu vào là
số có nghĩa là kết thúc bộ test
Dữ liệu ra
- Đối với mỗi truy vấn, bạn in ra một dòng chứa độ dài đường đi ngắn nhất từ đỉnh nguồn đến đỉnh trong câu truy vấn hoặc "Impossible" nếu không tồn tại đường đi hoặc "-Infinity" nếu có chu trình âm trên đường đi.
Ràng buộc
Input 1
Sao chép
5 4 3 0
0 1 999
1 2 -2
2 1 1
0 3 2
1
3
4
2 1 1 0
0 1 -100
1
0 0 0 0
Output 1
Sao chép
-Infinity
2
Impossible
-100
Nhận xét