【LeetCode 815】公交路线

/*
难度：困难
给定一个数组routes，表示一系列公交线路，其中每个routes[i]表示一条公交线路，第i辆公交车将会在上面循环行驶。
例如：routes[0]=[1,5,7]表示第0辆公交车会一直按序列1->5->7->1->5->7->...这样的车站路线行驶。
现在从source车站出发（初始时不在公交车上），要前往target车站，且期间仅可乘坐公交车。
求出最少乘坐的公交车数量，如果不可能到达终点车站，返回-1.示例：
输入：routes=[[1,2,7], [3,6,7]], source=1, target=6
输出：2示例：
输入：routes=[[7,12], [4,5,15], [6], [15,19], [9,12,13]], source=15, target=12
输出：-1提示：
routes数组长度不超过500
routes的子数组长度不超过10^5
routes[i]中的所有值互不相同
sum(routes[i].length) < 10^5
routes[i][j] < 10^6
*/ 
class MNode: Hashable, Equatable {var code: Intvar mappedstats = [Int:Int]() //以车站编号为key，value可以任意，存在即可var con = Set<MNode>()init(code: Int) {self.code = code}static func == (lhs: MNode, rhs: MNode) -> Bool {return lhs.code == rhs.code}func hash(into hasher: inout Hasher) {hasher.combine(code)}
}
extension Daily {static func test_leetcode815() {var routes = [[Int]]()var idx = 0while idx < 9000 {var sublist = [Int]()var sidx = 0while sidx < 301 {sublist.append(idx)sidx += 1idx += 1}routes.append(sublist)idx -= 1}let source = 0, target = 90000		for sublist in routes {print(sublist)}let start = NSDate.nowprint("开始时间 \(NSDate.now)")let res = Daily.leetcode815(routes, source, target)let end = NSDate.nowprint("输出：\(res), 耗时 \(end.timeIntervalSince(start))\n")}static func leetcode815(_ routes: [[Int]], _ source: Int, _ target: Int) -> Int {if source == target {return 0}var net = [MNode]()var contain = [MNode]()//建立nodefor idx in 0..<routes.count {let item = routes[idx]let node = MNode(code: idx)for astation in item {node.mappedstats[astation] = 1}net.append(node)if node.mappedstats[source] == 1 {contain.append(node)}}//node之间建立连接var slmap = [Int:[Int]]()for node in net {let sts = node.mappedstats.keysfor station in sts {if slmap[station] == nil {slmap[station] = [node.code]}else {slmap[station]!.append(node.code) }}}for (_, list) in slmap {if list.count < 2 {continue}for idx in list {for subidx in list {if subidx != idx {net[idx].con.insert(net[subidx])}}}}let RMAX = net.count + 11 //只要大于net.count即可var minroute = RMAXfor sidx in 0..<contain.count {let node = contain[sidx]if node.mappedstats[target] == 1 {minroute = 0break}var map = [Int](repeating: RMAX, count: net.count)map[node.code] = 0var minnodes = [MNode]()for cnode in node.con {map[cnode.code] = 1}minnodes.append(contentsOf: node.con)var arrDone = [Int](repeating: 0, count: net.count)arrDone[node.code] = 1while minnodes.count > 0 {let minnode = minnodes.removeFirst()				arrDone[minnode.code] = 1let steps = map[minnode.code]for cnode in minnode.con {if arrDone[cnode.code] == 0 && map[cnode.code] > steps + 1 {map[cnode.code] = steps + 1minnodes.append(cnode)}}if minnode.mappedstats[target] == 1 {if map[minnode.code] < minroute {minroute = map[minnode.code]}break}}
//			print("\(node.code),  \(map)")}for item in net {item.con.removeAll()}return minroute == RMAX ? -1 : minroute + 1}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！