测试数据

n m x n个点 m个边 s起点

a b c a到b 权为c

4 5 3
3 1 6
3 2 1
2 1 1
2 4 5
1 4 3

5 5 1
1 4 2
1 5 5
4 3 2
5 3 -3
3 2 3

代码

package main

import (
	"bufio"
	"fmt"
	"os"
)

func _debug() {
	const eof = 0
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	_i, _n, buf := 0, 0, make([]byte, 1<<12) // 4KB

	// 读一个字符
	rc := func() byte {
		if _i == _n {
			_n, _ = os.Stdin.Read(buf)
			if _n == 0 { // EOF
				return eof
			}
			_i = 0
		}
		b := buf[_i]
		_i++
		return b
	}

	// 读一个整数，支持负数
	ri := func() (x int) {
		neg := false
		b := rc()
		for ; '0' > b || b > '9'; b = rc() {
			// 某些多组数据的题目，不告诉有多少组数据，那么需要额外判断是否读到了 EOF
			if b == eof {
				return
			}
			if b == '-' {
				neg = true
			}
		}
		for ; '0' <= b && b <= '9'; b = rc() {
			x = x*10 + int(b&15)
		}
		if neg {
			return -x
		}
		return
	}

	// bellman ford
	n, m, s := ri(), ri(), ri() // n个点 m个边 s起点

	graph := make([][]edge, n+1)

	for ; m > 0; m-- {
		a, b, c := ri(), ri(), ri()
		graph[a] = append(graph[a], edge{b, c})
	}

	dist := make([]int, n+1)
	for i := range dist {
		dist[i] = 1<<31 - 1
	}

	dist[s] = 0 // 起点

	var fg bool
	for i := 1; i <= n; i++ { // n 轮
		fg = false
		for u := 1; u <= n; u++ {
			if dist[u] == 1<<31-1 {
				continue
			}
			for _, e := range graph[u] { // u的出边
				if dist[e.to] > dist[u]+e.val {
					dist[e.to] = dist[u] + e.val
					fg = true
				}
			}
		}
		if !fg {
			break
		}
	}

	fmt.Fprintln(out, dist)

	// 为true则有环
	fmt.Fprintln(out, fg)
}

type edge struct {
	to  int
	val int
}

func main() {
	_debug()
}