Lan Truyền Chu Trình Âm Đa Nguồn

Buổi 41 — SPFA & Bellman-Ford
Points
85
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho một đồ thị có hướng gồm N đỉnh và M cạnh có trọng số (có thể âm) cùng với tập K đỉnh nguồn s_1, s_2, ..., s_K. Bạn có thể xuất phát từ bất kỳ đỉnh nguồn nào với chi phí ban đầu bằng 0. Với mỗi đỉnh v từ 1 đến N, gọi d[v] là chi phí nhỏ nhất để đi từ một trong các nguồn tới v (-∞ nếu có thể giảm vô hạn qua chu trình âm, hoặc không đi tới được). Hãy thống kê 3 giá trị: số đỉnh có d[v] = -∞, số đỉnh không đi tới được, và tổng các giá trị d[v] hữu hạn lấy dư theo 1000000007 (số dư không âm trong [0, 1000000006]).

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên N và M.
  • M dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, w.
  • Dòng tiếp theo chứa số nguyên K.
  • Dòng cuối cùng chứa K số nguyên s_1, s_2, ..., s_K.
Dữ liệu ra
  • Ba số nguyên trên một dòng: số đỉnh -∞, số đỉnh không tới được, và tổng các khoảng cách hữu hạn modulo 1000000007.
Ví dụ
Input Output
5 5
1 2 2
2 3 -5
3 2 1
4 5 -10
5 1 100
2
1 4
2 0 999999997
5 3
1 2 -3
2 3 5
4 5 1
1
1
0 2 1000000006
Giới hạn
  • 1 ≤ N ≤ 3000
  • 0 ≤ M ≤ 10000
  • 1 ≤ K ≤ N
  • -10^9 ≤ w ≤ 10^9
Draft saved