network-delay-time.go

// https://leetcode.com/problems/network-delay-time

const inf = (1 << 31) - 1

type Edge struct {
    vertex int
    time int
}

func networkDelayTime(times [][]int, N int, K int) int {
    graph := make([][]Edge, N + 1)
    
    for _, item := range times {
        from, to, time := item[0], item[1], item[2]
        graph[from] = append(graph[from], Edge{to, time})
    }
    
    path := findMaxPath(graph, K)
    
    if path == inf {
        path = -1
    }
    
    return path
}

func findMaxPath(graph [][]Edge, from int) int {
    distances := make([]int, len(graph))
    visited := make([]bool, len(graph))
    
    for i, _ := range distances {
        distances[i] = inf
    }
    
    distances[from] = 0
    
    for i := 1; i < len(graph); i++ {
        anchor := 0
        
        // vertex from unvisited with minimum time
        for j := 1; j < len(graph); j++ {
            if !visited[j] && (anchor == 0 || distances[anchor] > distances[j]) {
                anchor = j
            }
        }
        
        visited[anchor] = true
        
        if distances[anchor] == inf {
            break
        }
        
        for _, child := range graph[anchor] {
            distances[child.vertex] = min(distances[child.vertex], distances[anchor] + child.time)
        }
    }
    
    
    maxPath := 0
    
    for _, distance := range distances[1:] {
        maxPath = max(distance, maxPath)
    }
    
    return maxPath
}

func min(a, b int) int {
    if a < b {
        return a
    }
    
    return b
}

func max(a, b int) int {
    if a < b {
        return b
    }
    
    return a
}