题目描述

输入边[sr,dst]，求1到n的最短路径

思想

宽度搜索，依次在父节点距离值上加1

go 代码

package main
import "fmt"

func main(){
    var n,m int
    fmt.Scanf("%d %d",&n,&m)
    head :=make([][]int,n)

    for m>0{
        var start,end int
        fmt.Scanf("%d %d",&start,&end)
        // 作为脚标都要减1
        head[start-1] = append(head[start-1],end)
        m--
    }

    dst :=make([]int,n)

    q :=make([]int,0)
    q = append(q,1)
    for len(q) > 0 {
        st :=q[0]
        q =q[1:]

        for _,val :=range head[st-1]{
            if dst[val-1] == 0{
                dst[val-1] = dst[st-1] + 1
                q = append(q,val)
            }
        }
    }
    if dst[n-1] == 0{
        fmt.Println(-1)
    }else{
        fmt.Println(dst[n-1])
    }
}