Bellman-Ford

 1type edge struct{ v, to, co int }
 2
 3func bellmanFord(es []edge, n, s, inf int) ([]int, bool) {
 4	dist := make([]int, n)
 5	for i := 0; i < n; i++ {
 6		dist[i] = inf
 7	}
 8	dist[s] = 0
 9	for i := 0; i < n-1; i++ {
10		for _, e := range es {
11			if dist[e.v] != inf && dist[e.to] > dist[e.v]+e.co {
12				dist[e.to] = dist[e.v] + e.co
13			}
14		}
15	}
16	cycle := false
17	for _, e := range es {
18		if dist[e.v] != inf && dist[e.to] > dist[e.v]+e.co {
19			cycle = true
20		}
21	}
22	return dist, cycle
23}
24