最短路

判断负环测试数据

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

Yes

5 10
2 1 10
3 1 3
4 1 2
2 4 10
5 5 1
5 2 2
2 2 1
2 4 8
1 2 10
3 4 9

No

判断负环代码

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
	}

	// spfa判断环
	n, m := 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})
	}
	// 加入一个虚拟点 连向所有边的权均为0 然后再做spfa
	for i := 0; i <= n; i++ {
		graph[0] = append(graph[0], edge{i, 0})
	}

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

	vis := make([]bool, n+1)
	cnt := make([]int, n+1)
	q := []int{}

	for i := 1; i <= n; i++ {
		q = append(q, i)
		vis[i] = true
	}

	for len(q) != 0 {
		u := q[0]
		q = q[1:]
		vis[u] = false

		for _, ed := range graph[u] {
			v := ed.to
			w := ed.val
			if dist[v] > dist[u]+w {
				dist[v] = dist[u] + w
				cnt[v] = cnt[u] + 1 // 记录边数
				if cnt[v] >= n {
					fmt.Fprintln(out, "Yes")
					return
				}
				if !vis[v] {
					q = append(q, v)
					vis[v] = true
				}
			}
		}
	}

	fmt.Fprintln(out, "No")
}

type edge struct {
	to  int
	val int
}

func main() {
	_debug()
}