Dữ liệu đầu vào cho một đồ thị có hướng có trọng số gồm nút và cạnh. Yêu cầu bạn viết chương trình để xác định xem trong đồ thị này có tồn tại chu trình âm (negative cycle) hay không. Nếu từ một điểm xuất phát đi theo một đường dẫn nào đó và quay lại chính nó, mà tổng trọng số các cạnh đi qua nhỏ hơn , thì đường đó được gọi là một chu trình âm.
Nếu tồn tại chu trình âm, chỉ xuất ra một dòng chứa số . Nếu không tồn tại chu trình âm, hãy tính độ dài đường đi ngắn nhất từ một điểm cho trước đến tất cả các điểm khác. Quy ước: khoảng cách từ đến là , nếu không liên thông với điểm nào đó thì xuất NoPath.
Dữ liệu:
Dòng đầu tiên chứa ba số nguyên dương, lần lượt là số điểm , số cạnh , và điểm nguồn .
dòng tiếp theo, mỗi dòng chứa ba số nguyên , biểu thị có một cạnh nối từ điểm đến điểm với trọng số là .
Kết quả:
Nếu tồn tại chu trình âm, chỉ xuất ra một dòng . Ngược lại, xuất theo định dạng sau:
Gồm dòng, dòng thứ mô tả đường đi ngắn nhất từ đến :
Nếu và không liên thông, xuất NoPath.
Nếu , xuất .
Các trường hợp khác, xuất độ dài đường đi ngắn nhất từ đến .
