solution

Một quân cờ xuất phát ở đỉnh $0$ của một DAG $n$ đỉnh. Tại đỉnh $u$, nếu có các cung ra $(u\to v)$ với trọng số $w$, quân cờ đi tới $v$ với xác suất $w / \big(\sum w\big)$ (tổng theo mọi cung ra của $u$). Nếu $u$ không có cung ra và $u \ne n-1$ thì quân cờ dừng (thất bại).

Tính xác suất quân cờ tới được đỉnh đích $n-1$. In dưới dạng phân số tối giản p/q, hoặc in số nguyên nếu mẫu bằng $1$.