a.go

package main
import "fmt"

// [[1, 2, 7], [3, 6, 7]]
// given a src and dest stop, what is the minimum number of hops?

// src: 2 dst:3
// r0 8->3
// r1 7->8
// r2 1->2->7
// r3 3->6->7

// undirected graph search while keeeping cost min
// * loops
// * dfs/bfs
// 1--2--7*-8*-
// 3--6-/*    |
// ^-----------

// rn -> rm  N stops
// src: r1 r2 d: r3 .. r10

// [[1, 2, 7], [3, 6, 7]]
func f(routes [][]int, srcStop, dstStop int) int {
    stopsToRoutes := make(map[int][]int)
    for routeID , stops := range routes {
        for _, stop := range stops {
            stopsToRoutes[stop] = append(stopsToRoutes[stop], routeID)
        }
    }
    
    connectingRoutes := make(map[int][]int)
    for routeID, stops := range routes {
        for _, stop := range stops {
            routesOnThisStop := stops[stop]
                for _, r := range routesOnThisStop {
                    if r != routeID {
                        connectingRoutes[routeID] = r
                    }
                }
            }
        }
    }
    
    // min hops between srcRoutes and dstRoutes pairs
    
    var minOut = math.MaxInt32 
    for _, srcRoute := range srcRoutes {
        for _, dstRoute := range dstRoutes {
            if srcRoute == dstRoute {
                minOut = 0
                break
            }
            minOut = min(minOut, minRouteHops(graph, srcRoute,dstRoute))
        }
    }
    if minOut == math.MaxInt32 {
        minOut = -1
    }
    return minOut
}

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

func minRouteHops(graph make(map[int][]int), srcRoute, dstRoute int) int {
    visited := make(map[int]bool)
    return dfs(graph, dstRoute, srcRoute, visited, 0)
}

func dfs(graph make(map[int][]int), dst int, cur int, visited map[int]bool, hops int){
    if cur == dst {
        return hops
    }
    
    visited[cur]=true
    defer visited[cur]=false 
    
    var minHop = math.MaxInt
    
    for _, neighbor := range graph[cur] {
        if visited[cur] {
            continue
        }
        if gotHops := dfs(graph, dst, neighbor, visited, hops+1); gotHops != -1 {
            minHop = min(minHop,gotHops)
        }
    }
    return minHop
}

// stops --> []routes
// 3 -> r0, r3

// route --> set(route)
// r2 <> r1
// r1 <> r0
// r2 <> r3

// src: s2 dst: s3
// search src:r2 dst: r0
// search src:r2 dst: r3

// graph (src->dst) bfs
// 2 <--> 1 <--> 0
// ^
// v
// 3

func main() {
    c1 := []int{[]int[1, 2, 7], []int[3, 6, 7]}
    fmt.Println(f(c1,2,3))
}