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 \(4\) số nguyên không âm \(n,m,q,s\). Trong đó \(n\) là số đỉnh được đánh số từ \(0\) đế \(n-1\), \(m\) là số cạnh, \(q\) là số lượng câu truy vấn, \(s\) là đỉnh bắt đầu. Tiếp theo là \(m\) dòng, mỗi dòng chứa \(3\) số nguyên \(u,v,w\) là cạnh nối đỉnh \(u\) đến \(v\) có trọng số là \(w\). Theo sau là \(q\) 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ừ \(s\) đến đỉnh đó.
- Nếu dữ liệu vào là \(4\) số \(0\) 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
- \(1 \le n \le 1000\)
- \(1 \le m \le 5000\)
- \(1 \le q \le 100\)
- \(-2000 \le w \le 2000\)
Input 1
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
-Infinity
2
Impossible
-100
Nhận xét