// 设置标准输入接口
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