/ Vijos / 题库 /

寻路

寻路

时间限制:1秒  内存限制:256M


【题目描述】

  贝西被困在一个荒凉的北极岛屿,她可以用小船乘着海流用 1 单位时间从一个岛移动到另一个岛。

  她得到了一个海洋地图,有 \(N\) 条单向海流航线,编号为 \(1 .. N\)。

  告诉你她的起始位置 \(S\) 和地图,帮助贝西确定到达每个岛的最短时间是多少。

  输入为一个矩阵 \(C\),第 \(r\) 行,第 \(c\) 列的值若为 1,则 \(r\) 到 \(c\) 存在海流,值为 0 则不存在海流。

【输入格式】

  第 1 行:两个用空格隔开的整数:\(N\) 和 \(S\)
  第 \(2 .. N +1\):第 \(i +1\) 行包含 \(N\) 个用空格隔开的整数,表示矩阵 \(C\),矩阵 \(C\) 的 \(r\) 行第 \(c\) 列的值若为 1,则 \(r\) 到 \(c\) 存在海流,值为 0 则不存在海流。。

【输出格式】

  第1 ..??行:第一行输出 \(S\),第 \(i +1\) 行包含时刻 \(i\) 能到达的岛屿(升序排列)

【输入输出样例】

 Input

4 1
0 1 0 1
0 0 1 0
0 0 0 1
0 0 0 0

 Output

1
2 4
3

【数据限制】

  对于 \(100\%\) 的数据,\(1≤N≤100\)。

【来源】

  Mr.he

信息

ID
2198
难度
(无)
分类
图结构 | 最短路 点击显示
标签
递交数
0
已通过
0
通过率
?
被复制
4
上传者