简答题
偏难
#7054
漫漫回国路 2020年5月,国际航班机票难求。一位在美国华盛顿的中国留学生,因为一些原因必须在本周内回到北京。现在已知各个机场之间的航班情况,求问他回不回得来(…
漫漫回国路
2020年5月,国际航班机票难求。一位在美国华盛顿的中国留学生,因为一些原因必须在本周内回到北京。现在已知各个机场之间的航班情况,求问他回不回得来(不考虑转机次数和机票价格)。
时间限制:1000
内存限制:65536
输入
第一行为case个数n(n < 10)。 每一个case,第一行为机场个数N,N ≤ 10。 之后的N行,每一行包含N个整数。第i(1 ≤ i ≤ N)行的第j(1 ≤ j ≤ N)个整数代表从第i个机场出发到第j个机场的能买到的航班的最低票价t(0 < t < 10000)。如果不幸没有航班,那么用-1表示。第i行第i个整数为0。 起点华盛顿杜勒斯国际机场的编号为1,终点北京首都国际机场的编号为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
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">// 广搜
#include <bits/stdc++.h>
using namespace std;
int a[12][12], n;
bool v[12][12];
bool bfs(int p) {
queue<int> q;
q.push(p);
v[p][p] = true;
while (!q.empty()) {
int h = q.front();
q.pop();
for (int i = 1; i <= n; i++) {
if (!v[h][i] && a[h][i] > 0) {
if (i == n)
return true;
else {
q.push(i);
v[h][i] = true;
}
}
}
}
return false;
}
int main() {
int k;
cin >> k;
while (k--) {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
if (bfs(1))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">// 参考代码2
// 深度优先搜索
#include <stdbool.h>
#include <stdio.h>
#define MAX_N 10
#define INF 10000
int airports[MAX_N][MAX_N]; // 存储机场之间的航班票价
bool visited[MAX_N]; // 记录机场是否被访问过
int n; // 机场个数
bool found; // 是否找到回国路径
void dfs(int start, int end) {
if (start == end) {
found = true; // 找到回国路径
return;
}
visited[start] = true;
for (int i = 1; i <= n; i++) {
if (!visited[i] && airports[start][i] != -1) {
dfs(i, end);
}
}
}
bool canReturn() {
found = false;
for (int i = 1; i <= n; i++) {
visited[i] = false;
}
dfs(1, n);
return found;
}
int main() {
int cases;
scanf("%d", &cases);
while (cases--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &airports[i][j]);
}
}
if (canReturn()) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}</pre><p><br/></p>
这道题暂未补解析。