编辑代码

// 设置标准输入接口
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

// 问题描述:在一个有向图中找到从指定起点出发的最大权值路径
// 输入格式:
// n: 节点数量
// 接下来n行:每行n个数字,表示邻接矩阵
//   - matrix[i][i]表示节点i的权值
//   - matrix[i][j]=1表示i到j有边,0表示无边
// k: 起始节点编号(1-based)

void (async function () {
  // 读取节点数量
  const n = Number(await readline());

  // 读取邻接矩阵
  const matrix = [];
  for (let i = 0; i < n; i++) {
    matrix.push((await readline()).split(" ").map(Number));
  }

  // 读取起始节点编号
  const k = Number(await readline());

  // 深度优先搜索函数
  // 参数 i: 当前访问的节点索引
  // 返回值: 从当前节点出发能获得的最大路径权值和
  const dfs = (i) => {
    // 获取当前节点的权值
    let sum = matrix[i][i];

    // 记录所有子路径中的最大权值和
    let max = 0;

    // 遍历所有可能的下一个节点
    for (let j = 0; j < n; j++) {
      // 跳过自身和无边相连的节点
      if (j == i || matrix[i][j] == 0) continue;

      // 如果有边相连,递归访问该节点
      if (matrix[i][j] == 1) {
        // 更新最大子路径权值和
        max = Math.max(max, dfs(j));
      }
    }

    // 返回当前节点权值加上最大子路径权值和
    return sum + max;
  };

  // 从k-1节点开始搜索(转换为0-based索引)
  const res = dfs(k - 1);
  // 输出结果
  console.log(res);
})();

// 示例说明:
// 输入:
// 3           // 3个节点
// 5 1 0      // 节点1的权值为5,可以到达节点2
// 0 7 1      // 节点2的权值为7,可以到达节点3
// 0 0 8      // 节点3的权值为8,无法到达其他节点
// 1           // 从节点1开始
// 输出:
// 20          // 最大路径为:节点1(5) -> 节点2(7) -> 节点3(8),总和=20