A46310. 漫漫回国路2020 年 5 月 ， 国际航班机票难求。 一位在美国华盛顿的中国留学生， 因为一些原因必须在本周内回到北京。 现在已知各个机场之间的航班情况， 求问他回不回得来（不考虑转机次数和机票价格） 。输入第一行为 case 个数 n(n < 1 0)。 每一个 case， 第一行为机场个数 N， N ≤ 1 0。 之后的N 行， 每一行包含 N 个整数。 第 i（1 ≤ i ≤ N） 行的…
题目描述
漫漫回国路
2020 年 5 月 ， 国际航班机票难求。 一位在美国华盛顿的中国留学生， 因为一些原因必须在本周内回到北京。 现在已知各个机场之间的航班情况， 求问他回不回得来（不考虑转机次数和机票价格） 。
输入
第一行为 case 个数 n(n < 1 0)。 每一个 case， 第一行为机场个数 N， N ≤ 1 0。 之后的N 行， 每一行包含 N 个整数。 第 i（1 ≤ i ≤ N） 行的第 j（1 ≤ j ≤ N） 个整数代表从第 i个机场出发到第 j 个机场的能买到的航班的最低票价 t（0 < t < 1 0000） 。 如果不幸没有航班， 那么用-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
参考答案
// 广搜
#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;
}答案解析
// 参考代码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;
}