基础

使用BFS思想优化Bellman Ford算法
写起来很像djikstra的算法，基本就是拿dijstra的模板来改一下就是了。

要说不同，spfa能有负边。

就试用体验来说，能用dijstra的都能用spfa，除非出题人卡时间

模板1：求最短路

仔细观察的话，会发现spfa有以下要素：
- 邻接表存储操作
- dijkstra招牌： if dist[j] > dist[t] + w[i] {dist[j] = dist[t] + w[i] ...}
- bfs的队列（入队尾候选出队头处理）操作

package main
import (
    "fmt"
    "os"
    "bufio"
    "strings"
    "strconv"
    )

const (
    N = 100010
    M = N
    INF = 1 << 31 - 1
    )

var (
    out = bufio.NewWriter(os.Stdout)
    in = bufio.NewScanner(os.Stdin)
    readLine = func() []int {
        in.Scan()
        l := strings.Split(in.Text(), " ")
        res := make([]int, len(l))
        for i, s := range l {
            x, _ := strconv.Atoi(s)
            res[i] = x
        }
        return res
    }

    idx int
    h [N]int
    e, ne, w [M]int

    dist, q [N]int
    st [N]bool
    n, m int
    )

func add(a, b, c int) {
    e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx; idx++
}

func spfa() int {
    dist[0] = INF; for i := 1; i < N; i *= 2 {copy(dist[i:], dist[:i])}
    dist[1] = 0 

    hh, tt := 0, -1
    tt++; q[tt] = 1

    for hh <=  tt {
        t := q[hh]; hh++ 
        if hh == N {hh = 0} // 防止超时的限制
        st[t] = false 

        for i := h[t]; i != -1; i = ne[i] {
            j := e[i] 
            if dist[j] > dist[t] + w[i] {
                dist[j] = dist[t] + w[i]
                if !st[j] {
                    tt++; q[tt] = j
                    if tt == N {tt = 0} // 防止超时的限制
                    st[j] = true
                }
            }
        }
    }
    return dist[n]
}

func main() {
    defer out.Flush()
    cur := readLine()
    n, m = cur[0], cur[1]
    h[0] = -1; for i := 1; i < N; i *= 2 {copy(h[i:], h[:i])}
    for; m > 0; m-- {
        tmp := readLine()
        a, b, c := tmp[0], tmp[1], tmp[2]
        add(a, b, c)
    }

    res := spfa()
    if res == INF {
        fmt.Fprintln(out, "impossible")
    } else {
        fmt.Fprintln(out, res)
    }
}

模板2：求是否存在负边

抽屉原理
在更新dist时（1 - x的最短距离），同时计算cnt（1 - x最短路的边数）
在计算过程中，cnt[x] >= n（n条边， n + 1个点，但是题目是n个点，说明图中存在负权环了），返回true

spfa算法的另一用途。其中关键是，在队列中要先把所有的点先存进入，一个个取队头。
在这里还用模板1的全范围数组会出现奇怪的bug，而用go的切片反而能稳定运算

因为就只是在算边数，不用算dist数组，因此不用初始化dist

package main
import (
    "fmt"
    "strings"
    "strconv"
    "os"
    "bufio"
    )

const (
    N = 2010
    M = 10010
    INF = 1 << 31 - 1
    )

var (
    out = bufio.NewWriter(os.Stdout)
    in = bufio.NewScanner(os.Stdin)
    bs = make([]byte, 20000 * 1024)
    readLine = func() []int {
        in.Scan()
        l := strings.Split(in.Text(), " ")
        res := make([]int, N)
        for i, s := range l {
            x, _ := strconv.Atoi(s)
            res[i] = x
        }
        return res
    }

    idx int 
    h [N]int
    e, ne, w [M]int

    dist, cnt [N]int
    st [N]bool

    n, m int
    )

func add(a, b, c int) {
    e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx; idx++
}

func spfa() bool {
    q := make([]int, 0, N)

    // 有可能从1开始都走不到负环
    // 那就把所有点都放进去spfa一遍就好了
    for i := 1; i <= n; i++ { 
        st[i] = true
        q = append(q, i)
    }

    for len(q) > 0 {
        t := q[0]; q = q[1:]
        st[t] = false        

        for i := h[t]; i != -1; i = ne[i] {
            j := e[i] 
            if dist[j] > dist[t] + w[i] {
                dist[j] = dist[t] + w[i]
                cnt[j] = cnt[t] + 1 // key

                if cnt[j] >= n {return true} // key

                if !st[j] {
                    q = append(q, j)
                    st[j] = true
                }
            }
        }
    }
    return false
}

func main() {
    defer out.Flush()
    in.Buffer(bs, len(bs))
    cur := readLine()
    n, m = cur[0], cur[1]

    h[0] = -1; for i := 1; i < N; i *= 2 {copy(h[i:], h[:i])}

    for ; m > 0; m-- {
        tmp := readLine()
        a, b, c := tmp[0], tmp[1], tmp[2]
        add(a, b, c)
    }

    if !spfa() {
        fmt.Fprintln(out, "No")
    } else {
        fmt.Fprintln(out, "Yes")
    }
}