23. 毕业旅行[200分]

题目内容

四年校园时光即将结束，小明和室友计划一次难忘的毕业旅行。他们准备从 A 城市出发，前往他们已经久仰的 B 城市。两座城市之间有多种出行方案，既可直达，也可途经其他城市中转，每条路线的费用不相同。请帮助他们在预算 w 内，找到花费最少的路线。

输入描述

第一行有三个整数 n, m, w：

• n：城市数量，2 ≤ n ≤ 100
• m：路线数量，1 ≤ m ≤ 1000
• w：最大预算，1 ≤ w ≤ 10^5

接下来是一个二维数组，记录了所有的路线信息。每条路线有 3 个整数 u, v, cost：

• u：起点城市，1 ≤ u ≤ n
• v：终点城市，1 ≤ v ≤ n
• cost：所需费用，1 ≤ cost ≤ 10^5

输出描述

若存在满足预算的最优路线，返回最小花费；若不存在，则返回 -1。

补充说明：

• 出发城市编号为 1，目的地城市编号为 n 所代表的值。
• 每条路线的起点和终点都不相同（u ≠ v），且只能单方向通行（u → v，不能 v → u）。
• 从城市 u 到城市 v，不存在多条不同费用的路线。

样例

样例 1

输入

3 3 10
1 2 5
2 3 5
1 3 8

输出

8

说明：

• 直达：城市 1 → 城市 3，花费 8，在预算内最优。
• 中转：途经城市 2，花费 5 + 5 = 10，费用更高。

样例 2

输入

4 4 20
1 2 5
2 3 5
3 4 5
1 4 25

输出

15

说明：

• 直达：城市 1 → 城市 4，花费 25，超出预算。
• 中转：路径 1 → 2 → 3 → 4，花费 15，为最小可行方案。

样例 3

输入

3 3 5
1 2 3
2 3 3
1 3 10

输出

-1

说明： 所有可行路径都超过预算 5，返回 -1 表示无解。

代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let inputs = [];
rl.on('line', (input) => {
    inputs.push(input);
});
rl.on('close', () => {
    const [n, m, w] = inputs[0].split(' ').map(Number);
    const list = [];
    inputs.forEach((item, index) => {
        if (index > 0) {
            list.push(item.split(' ').map(Number));
        }
    });
    // console.log(n, m, w, list);
    const used = Array(m).fill(false);
    let best = Infinity;
    const dfs = (x, nums) => {
        if (nums > w) return;
        if (nums > best) return;
        if (x === n) {
            // console.log(nums);
            best = Math.min(best, nums);
            return;
        }
        for (let i = 0; i < list.length; i++) {
            let [u, v, cost] = list[i];
            if (u === x && !used[i]) {
                used[i] = true;
                nums += cost;
                dfs(v, nums);
                used[i] = false;
                nums -= cost;
            }
        }
    };
    dfs(1, 0);
    console.log(best === Infinity ? '-1' : best);
});