Hệ Thống Ống Dẫn SPFA-SLF

Buổi 41 — SPFA & Bellman-Ford
Points
45
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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
Draft saved