一、 第一题 按条件连接岛屿(造桥)

// 模拟read_line
let read_line = (function (){
    let i = 0
    let data = [
        '2',
        '4 2 400',
        '1 2 200',
        '3 4 300',
        '3 3 400',
        '1 2 500',
        '1 3 600',
        '2 3 700',
        ]
    return function (){
        return data[i++]
    }
})()

main()

function main(args){
    let T = read_line()
    for(let i=0;i<T;i++){
        console.log(resolve())
    }
}

function resolve(){
    let args = read_line().split(' ').map(e=>parseInt(e))
    let N = args[0] // 小岛数目
    let M = args[1] // 边数
    let maxPrice = args[2] //最大成本

    // 定义数据树 { '1': { '2': 500, '3': 600 }, '2': { '3': 700 } }
    let TREE = {}
    for (let index = 0; index < M; index++) {
        let p = read_line().split(' ').map(e=>parseInt(e))
        let begin = p[0],end = p[1],price = p[2]
        if(TREE[begin]) TREE[begin][end] = price
        else{
            TREE[begin] = {
                [end]:price
            }
        }
    }
    // 结果状态树，存放满足最大成本的小岛为key
    let result = {}
    // 存放当前的已构建的桥数
    let sideCount = 0
    // 根据数据树 遍历小岛起点
    for (const begin in TREE) {
        if (TREE.hasOwnProperty(begin)) {
            const ends = TREE[begin]
            // 遍历小岛终点
            for (const end in ends) {
                if (ends.hasOwnProperty(end)) {
                    const element = ends[end]

                    if(element <= maxPrice){ //小于等于最大成本
                        // 将两个小岛都存放到结果树中
                        result[begin] = result[end] = true
                        // 增加桥数
                        sideCount++
                        // 如果当前结果树中，节点个数正好与N要求一致，并且边数正好是节点个数减一（防止1->2,3->4出现的错误） 则返回"Yes"
                        if(Object.keys(result).length === N && sideCount == N-1) return "Yes"
                    }
                }
            }
        }
    }
    return "No"
}

第二题 根据建立的有向图，计算顶点A到顶点B的最小成本时长，按规定计算抵达终点的时间。

let read_line = (function (){
    let i = 0
    // let data = [
    //     '4 4',
    //     '1 2 25',
    //     '1 3 18',
    //     '2 4 28',
    //     '3 4 22',
    //     '1 4 9.1/8',
    //     ]
    let data = [
        '4 4',
        '1 2 5',
        '1 3 6',
        '2 4 8',
        '3 4 6',
        '1 4 7.9/8',
        ]
    return function (){
        return data[i++]
    }
})()

function main(){
    let args = read_line().split(' ')
    let N = args[0]
    let M = args[1]

    // 默认为最大time
    let result = 1000000000000000
    let TREE = {}
    for(let i=0;i<M;i++){
        let p = read_line().split(' ').map(e=>parseInt(e))
        let begin = p[0],end = p[1],time = p[2]
        if(TREE[begin])TREE[begin][end] = time
        else{
            TREE[begin] = {
                [end]:time
            }
        }
    }
    // 获取起点、终点和时间
    let p = read_line().split(' ')
    let Begin = p[0],End = p[1],BeginTime = p[2]
    // 构建回溯函数
    function resolve(begin,end,tree,price){
        // console.log('begin,end,tree,price: ', begin,end,tree,price);
        if(!tree[begin])return

        for (const key in tree[begin]) {
            if (tree[begin].hasOwnProperty(key)) {
                const element = tree[begin][key];
                // 找到终点
                if(key == end && price+element<result){
                    result = price+element
                    continue
                }
                if(key != end && price+element < result){
                    resolve(key,end,tree,price+element)
                }
            }
        }
    }
    // 获取最小需要花费的时间 => result
    resolve(Begin,End,TREE,0)

    // 返回值为加了result时间后的时间字符串
    function addHour(time,hours){
        let [month,day,hour] = time.split(/[\.\/]/)
        let resHour = parseInt(hour)+parseInt(hours)
        let a = new Date(2020,month-1,parseInt(day)+parseInt(resHour/24),resHour%24)
        return `${a.getMonth()+1}.${a.getDate()}/${a.getHours()}`

    }
    console.log(addHour(BeginTime,result))

}



main()