完美笔试 有向图最短路径

// 1000->1020->1040->1050(100)

let read_line = (() => {
    let arr = ['1000 1050', '1000 1020 50', '1000 1030 70', '1020 1030 15', '1020 1040 30', '1030 1050 40', '1040 1050 20'];
    let i = 0;

    return _ => {
        return arr[i++];
    }
})();

let print = console.log;

class TreeNode {
    version: number;
    path: Path[];

    constructor(version: number) {
        this.version = version;
        this.path = [];
    }
}

class Path {
    start: number;
    target: number;
    length: number;

    constructor(start: number, target: number, length: number) {
        this.start = start;
        this.target = target;
        this.length = length;
    }
}


class _Array extends Array {
    has(item) {
        return !!this.find(v => {
            if (v === item) {
                return true;
            }
            return false;
        })
    }

    static clone(target) {
        let arr = new _Array(target.length);
        for (let key in target) {
            if (typeof target[key] === 'Object') {
                arr[key] = this.clone(target[key]);
                continue;
            }
            arr[key] = target[key];
        }

        return arr;
    }
}


function buildTree(startVersion, targetVersion, size) {
    let path = new Path(startVersion, targetVersion, size);

    if (!map.has(startVersion)) {
        map.set(startVersion, new TreeNode(startVersion))
    }

    map.get(startVersion).path.push(path);
}

let userVersion: number, latestVersion: number;
[userVersion, latestVersion] = read_line().split(' ').map(v => {
    return +v;
});

let line: string;
let map = new Map<number, TreeNode>();
while (line = read_line()) {
    buildTree.apply(null, line.split(' ').map(v => {
        return +v;
    }));
}

let startNode = map.get(userVersion);
let hasWalked = new _Array();
let result = walk(startNode, hasWalked, 0);

print(result);


function walk(node: TreeNode, hasWalked: _Array, hasWalkedLength: number): number {
    hasWalked.push(node.version);

    let results = [];
    node.path.forEach(path => {
        let hasWalkedForThisPath = _Array.clone(hasWalked);
        let hasWalkedLengthForThisPath = hasWalkedLength;

        if (hasWalkedForThisPath.has(path.target)) {
            return;
        }

        if (path.target === latestVersion) {
            hasWalkedLengthForThisPath += path.length;
        } else {
            hasWalkedLengthForThisPath += path.length + walk(map.get(path.target), hasWalkedForThisPath, hasWalkedLengthForThisPath);
        }

        results.push(hasWalkedLengthForThisPath);
    })

    return Math.min.apply(null, results);
}



// 完美世界2017校园招聘 技术综合B卷 在线考试
// 编程题 | 20分 1/2
// 最短最优升级路径
// 时间限制：C/C++语言 1000MS；其他语言 3000MS
// 内存限制：C/C++语言 65536KB；其他语言 589824KB
// 题目描述：
// 游戏网站提供若干升级补丁，每个补丁大小不一，玩家要升级到最新版，如何选择下载哪些补丁下载量最小。
// 输入
// 第一行输入                        第一个数为用户版本  第二个数为最新版本，空格分开
// 接着输入N行补丁数据        第一个数补丁开始版本 第二个数为补丁结束版本 第三个数为补丁大小，空格分开
// 输出
// 对于每个测试实例，输出一个升级路径以及最后实际升级的大小

// 样例输入
// 1000 1050
// 1000 1020 50
// 1000 1030 70
// 1020 1030 15
// 1020 1040 30
// 1030 1050 40
// 1040 1050 20
// 样例输出
// 1000->1020->1040->1050(100)