Truy vấn đường đi

Xem dưới dạng PDF

Gửi bài giải

Điểm: 100
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M

Tác giả:
Kiểu bài tập

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 đế n1, 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

  • 1n1000
  • 1m5000
  • 1q100
  • 2000w2000

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

Không có ý kiến tại thời điểm này.