1.漫漫回国路2020年5月，国际航班机票难求。一位在美国华盛顿的中国留学生，因为一些原因必须在本周

1.漫漫回国路
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
```

解析：

【喵呜刷题小喵解析】本题是一道典型的图论问题，可以使用Dijkstra算法求解。首先，我们需要从输入中读取机场个数N和各个机场之间的航班情况，存储在二维数组prices中。其中，prices[i][j]表示从第i个机场出发到第j个机场的航班最低票价，如果没有航班，则prices[i][j]为-1。然后，我们需要使用Dijkstra算法找到从华盛顿出发到北京的最短路径。具体实现时，我们可以使用一个二维数组paths来存储从每个机场出发到每个机场的最短路径长度，初始时所有路径长度都为-1。然后，我们遍历所有的机场，对于每个机场，我们遍历所有的航班，如果存在从当前机场出发到目标机场的航班，则更新paths数组。接下来，我们使用Dijkstra算法找到从华盛顿出发到北京的最短路径。具体实现时，我们可以使用一个一维数组dist来存储从华盛顿出发到每个机场的最短路径长度，初始时所有路径长度都为无穷大。然后，我们遍历所有的机场，对于每个机场，我们找到当前未访问过的机场中路径长度最短的机场，然后更新其邻居机场的最短路径长度。最后，我们判断是否能够回国，如果能够回国，则输出字符串"YES"，否则输出字符串"NO"。具体实现时，我们可以判断dist[N-1]是否等于无穷大，如果不等于无穷大，则说明能够回国，否则无法回国。

答案：

解析：

最热门资讯

JAVA工程师面试指导--猎头内部资料

常见面试问题100问！