Thuật toán Bellman-Ford / SPFA tìm đường đi ngắn nhất và phát hiện chu trình âm

Mục tiêu kiến thức

• Hiểu nguyên lý nới lỏng cạnh (Edge Relaxation) của Bellman-Ford: Thực hiện nới lỏng N-1 lần trên toàn bộ M cạnh.
• Phát hiện chu trình âm: Nếu ở lần lặp thứ N vẫn có cạnh tiếp tục nới lỏng được, đồ thị chứa chu trình âm tới được từ đỉnh nguồn.
• Tối ưu hóa bằng SPFA (Shortest Path Faster Algorithm) với hàng đợi và mảng đếm số lần vào hàng đợi cnt[u] >= N.

Mô tả bài toán

Cho một đồ thị có hướng gồm N đỉnh (1 ≤ N ≤ 2500) và M cạnh (1 ≤ M ≤ 5000). Mỗi cạnh có trọng số w (có thể âm).

Hãy tìm đường đi ngắn nhất từ đỉnh nguồn 1 đến đỉnh đích N. Nếu tồn tại chu trình âm mà từ đỉnh 1 có thể đi tới chu trình đó và từ chu trình đó có thể đi tới đỉnh N (khiến khoảng cách tới N có thể giảm xuống -∞), in -INF. Nếu không có đường đi từ 1 tới N, in INF. Ngược lại in giá trị đường đi ngắn nhất.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ N ≤ 2500.
• 1 ≤ M ≤ 5000.
• -10⁹ ≤ w ≤ 10⁹.
• Thời gian chạy: 1000ms.
• Bộ nhớ tối đa: 256MB.