Hệ Thống Ống Dẫn SPFA-SLF
Points
45
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một đồ thị có hướng thưa gồm N đỉnh và M cạnh có trọng số (có thể âm, đảm bảo không có chu trình âm). Hãy tìm đường đi ngắn nhất dist[i] từ đỉnh 1 đến mọi đỉnh i (1 ≤ i ≤ N). Để xuất kết quả gọn nhẹ, hãy in ra số lượng đỉnh đi tới được từ 1 và tổng ∑ (i × (dist[i] mod 1000000007)) mod 1000000007 trên tất cả các đỉnh i đi tới được (lưu ý phép chia lấy dư trả về giá trị 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ữ liệu ra
- Hai số nguyên cách nhau bởi dấu cách: số lượng đỉnh đi tới được từ 1 và giá trị tổng modulo
1000000007.
Ví dụ
| Input | Output |
|---|---|
| 4 5 1 2 3 1 3 10 2 3 -5 3 4 2 2 4 4 |
4 0 |
| 4 2 1 2 -10 3 4 5 |
2 999999987 |
Giới hạn
- 1 ≤ N ≤ 50000
- 0 ≤ M ≤ 150000
- 1 ≤ u, v ≤ N
- -10^6 ≤ w ≤ 10^6
Community Discussion