Module: Ford-Bellman algorithm


Problem

3 /6


Bellman

Problem

Given a directed weighted graph with negative edges (no negative cycles).
Given a start and end vertex, define the minimum distance between them.
 
Input:
Given 4 numbers n, m, s, f - number of vertices, number of edges, start and end vertex (starting from 1), respectively.
The next m lines contain 3 numbers each - vertex 1, vertex 2 and the price of transition between vertices.
 
Output:
It is required to display one number - the answer to the task. If there is no answer, output Inf.
 
Examples
# Input Output
1
4 2 1 4    
1 2 100500
2 3 100500
Inf