Đường đi ngắn nhất từ một nguồn, trọng số không âm (Single Source Shortest Path, Non-Negative Weights)

Nguồn: Kattis

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một đồ thị có hướng gồm $n$ đỉnh, được đánh số từ $0$ đến $n-1$, và $m$ cạnh có trọng số không âm.

Mỗi cạnh được mô tả bởi ba số nguyên $u$, $v$, $w$, biểu thị một cạnh có hướng từ đỉnh $u$ đến đỉnh $v$ với trọng số $w$.

Một đỉnh $s$ được chọn làm đỉnh xuất phát. Có $q$ truy vấn, mỗi truy vấn cho một đỉnh $v$.

Với mỗi truy vấn, hãy xác định tổng trọng số nhỏ nhất của một đường đi từ $s$ đến $v$.

Nếu không tồn tại đường đi từ $s$ đến $v$, cần thông báo rằng đỉnh $v$ không thể đạt tới từ $s$.

Input

Dòng đầu tiên chứa bốn số nguyên $n$, $m$, $q$, $s$, lần lượt là số đỉnh của đồ thị, số cạnh, số truy vấn và đỉnh xuất phát.

Trong $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u$, $v$, $w$, mô tả một cạnh có hướng từ đỉnh $u$ đến đỉnh $v$ với trọng số $w$.

Trong $q$ dòng tiếp theo, mỗi dòng chứa một số nguyên $v$, biểu thị một truy vấn yêu cầu tìm khoảng cách nhỏ nhất từ đỉnh $s$ đến đỉnh $v$.

Output

Với mỗi truy vấn, in ra một dòng chứa tổng trọng số nhỏ nhất của một đường đi từ đỉnh $s$ đến đỉnh được truy vấn.

Nếu không tồn tại đường đi như vậy, in ra:

Impossible

Các kết quả được in theo đúng thứ tự xuất hiện của các truy vấn trong dữ liệu vào.

Subtask

• Subtask 1 — 10%: $1 \le n \le 9$; $0 \le m \le 20$; $1 \le q \le 10$; $0 \le s,u,v<n$; $0 \le w \le 1000$.
• Subtask 2 — 15%: $1 \le n \le 200$; $0 \le m \le 3000$; $1 \le q \le 100$; $0 \le s,u,v<n$; $0 \le w \le 1000$.
• Subtask 3 — 20%: $1 \le n \le 1000$; $0 \le m \le 10^4$; $1 \le q \le 100$; $0 \le s,u,v<n$; $0 \le w \le 1000$.
• Subtask 4 — 25%: $1 \le n \le 5000$; $0 \le m \le 2\cdot10^4$; $1 \le q \le 100$; $0 \le s,u,v<n$; $0 \le w \le 1000$.
• Subtask 5 — 30%: $1 \le n \le 10^4$; $0 \le m \le 3\cdot10^4$; $1 \le q \le 100$; $0 \le s,u,v<n$; $0 \le w \le 1000$.

Ví dụ

Ví dụ 1

Input

4 3 4 0
0 1 2
1 2 2
3 0 2
0
1
2
3

Output

0
2
4
Impossible

Giải thích

Đồ thị có $4$ đỉnh, $3$ cạnh và đỉnh xuất phát là $0$.

Ba cạnh của đồ thị là:

• từ đỉnh $0$ đến đỉnh $1$ với trọng số $2$;
• từ đỉnh $1$ đến đỉnh $2$ với trọng số $2$;
• từ đỉnh $3$ đến đỉnh $0$ với trọng số $2$.

Đối với truy vấn đến đỉnh $0$, đỉnh cần đến cũng chính là đỉnh xuất phát nên khoảng cách bằng $0$.

Đối với truy vấn đến đỉnh $1$, có đường đi trực tiếp:

với tổng trọng số bằng $2$.

Đối với truy vấn đến đỉnh $2$, có đường đi:

với tổng trọng số:

Không tồn tại đường đi có hướng từ đỉnh $0$ đến đỉnh $3$. Cạnh nối hai đỉnh này có chiều từ $3$ đến $0$, vì vậy kết quả của truy vấn cuối cùng là Impossible.