题目

思路

DFS；
记录DFS到每个节点的时间arriveTime = make([]int, N+1, N+1)；
递归停止条件：如果arriveTime[x]不等于初始值-1，说明已经到达过改节点了，那是否要继续进行DFS呢？
需要看此次的到达时间是否比之前的到达时间小；

代码（超时了）

// DFS
// 用一个数组cost[N+1](N的范围是1~N)记录，当DFS到这个节点的时候，花了多长时间
// cont[N+1]初始值为-1
//
// times [][]int生成一个连接map
// 遍历到某个节点时，根据这个连接map，进行下一次的dfs
var linkMap map[int][][2]int
var arriveTime []int

func networkDelayTime(times [][]int, N int, K int) int {
    // 节点连接map
    linkMap = make(map[int][][2]int)
    for k := range times {
        if linkMap[times[k][0]] == nil {
            linkMap[times[k][0]] = make([][2]int, 0, 0)
        }
        linkMap[times[k][0]] = append(linkMap[times[k][0]], [2]int{times[k][1], times[k][2]})
    }

    //fmt.Printf("linkMap is %v\n", linkMap)

    // 记录到达时间
    arriveTime = make([]int, N+1, N+1)
    for k := range arriveTime {
        arriveTime[k] = -1
    }

    //fmt.Printf("linkMap is %v\n\n", linkMap)
    dfs(K, 0)
    //fmt.Printf("arriveTime is %v\n\n", arriveTime)

    max := arriveTime[1]
    for i:=1; i<=N; i++ {
        if arriveTime[i] == -1 {
            return -1
        }
        if arriveTime[i] > max {
            max = arriveTime[i]
        }
    }

    return max
}

func dfs(k int, reachTime int) {
    // fmt.Printf("dfs(%v)\n", k)
    // 递归停止条件: 访问过 && 此次的到达时间 > 大于之前的到达时间
    // 网状结构，不是树状结构，可能有多个可达路径
    // networkDelayTime([][]int{{1,2,1},{2,3,2},{1,3,2}}, 3, 1)
    if arriveTime[k] != -1 && reachTime > arriveTime[k] {
        return
    }

    arriveTime[k] = reachTime // 标志该节点已经被访问

    for _, node := range linkMap[k] {
        //fmt.Printf("node is %v\n", node)
        dfs(node[0], reachTime+ node[1])
    }
}