怎么往网站添加视频,大连市房屋管理局官方网站,东南亚vps,设计作品目录 T1. 漫漫回国路思路分析T2. 装箱问题思路分析T3. 鸣人和佐助思路分析T4. 分成互质组思路分析T1. 漫漫回国路
2020 年 5 月,国际航班一票难求。一位在美国华盛顿的中国留学生,因为一些原因必须在本周内回到北京。现在已知各个机场之间的航班情况,求问他回不回得来(不考… 目录 T1. 漫漫回国路思路分析 T2. 装箱问题思路分析 T3. 鸣人和佐助思路分析 T4. 分成互质组思路分析 T1. 漫漫回国路
2020 年 5 月,国际航班一票难求。一位在美国华盛顿的中国留学生,因为一些原因必须在本周内回到北京。现在已知各个机场之间的航班情况,求问他回不回得来(不考虑转机次数和机票价格)。
时间限制:1 s 内存限制:64 MB
输入 第一行为 case 个数 n ( n 10 ) n\ (n 10) n(n10)。 每一个 case,第一行为机场个数 N N N, N ≤ 10 N ≤ 10 N≤10。 之后的 N N N 行,每一行包含 N N N 个整数。第 i i i( 1 ≤ i ≤ N 1 ≤ i ≤ N 1≤i≤N)行的第 j j j( 1 ≤ j ≤ N 1 ≤ j ≤ N 1≤j≤N)个整数代表从第 i i i 个机场出发到第 j j j 个机场的能买到的航班的最低票价 t t t( 0 t 10000 0 t 10000 0t10000)。如果不幸没有航班,那么用 − 1 -1 −1 表示。 第 i i i 行第 i i i 个整数为 0 0 0。起点华盛顿杜勒斯国际机场的编号为 1 1 1,终点北京首都国际机场的编号为 N N N。输出 每一个 case 一行。能够回国,输出字符串 YES。如果无法回国,输出字符串 NO。样例输入2
3
0 100 -1
-1 0 200
-1 -1 0
4
0 1 5 -1
3 0 1 -1
2 4 0 -1
4 1 1 0样例输出YES
NO思路分析
此题考查搜索算法,属于基础题。
从起点 1 1 1 开始搜索,枚举从当前点 x x x 可以到达的任意点 i i i,如果从 x x x 到 i i i 存在航班且尚未走过,就乘坐该航班到达点 i i i,并从点 i i i 继续搜索,直至走到尽头或者终点 n n n 即可结束。用 D F S \tt DFS DFS 或 B F S \tt BFS BFS 均可实现。
/** Name: T1.cpp* Problem: 漫漫回国路* Author: Teacher Gao.* DateTime: 2025/01/03 00:21*/#include iostream
#include queueusing namespace std;bool bfs(int n, int a[][15])
{queueint Q;bool f[15][15] = {0};Q.push(1);while (!Q.empty())