Loading... 为了复习一下BFS和邻接表，出了这么一道~~水题~~。要注意的是，输入中可能存在~~很多~~环——所以DFS的处境就很鸡肋了——那么用BFS。 ## 题目描述 很久很久以前，有一只会飞的大象。有一天，大象在飞行过程中受伤了，只好迫降到一朵编号为1的云上。现在大象要去编号为m的童话云上的童话镇疗伤，它可以通过两朵云间的彩虹滑翔到另一朵云上。 现给出m（1 <= m <= 8000）朵云和n（m-1 <= n <= 10000）条单向彩虹，大象的初始体力值为v（1<=v<=n），每次滑翔会消耗1个单位的体力。如果它的体力值为0，就会因体力不支掉到地上。请你计算大象到达童话镇所剩的最大体力值，如果不能到达，请输出-1。 ## 输入 第1行3个整数m，n，v表示云和彩虹的数量、大象的初始体力值； 第2~n+1行每行2个整数a，b表示a有一条通向b的彩虹； ## 输出 输出一个整数，表示大象到达童话镇后剩余的最大体力值。 ## 输入样例1 > 4 5 5 > 1 2 > 2 1 > 1 3 > 3 2 > 2 4 ## 输出样例1 > 3 ## 输入样例2 > 5 5 2 > 1 3 > 3 4 > 4 2 > 2 5 > 2 4 ## 输出样例2 > -1 ## 参考代码 ``` #include <cstdio> #include <algorithm> #include <vector> #include <queue> using std::vector; using std::queue; int m, n, v; vector<int> r[8001]; queue<int> qu; int vis[8001]; int bfs(){ std::fill(vis, vis+m+1, 1e9); qu.push(1); vis[1] = v; while(!qu.empty()){ int x = qu.front(); qu.pop(); if(x == m) return vis[m]; for(int i = 0; i < r[x].size(); ++i){ if(vis[r[x][i]] == 1e9 && vis[x] >= 1){ qu.push(r[x][i]); vis[r[x][i]] = vis[x]-1; } } } return -1; } int main(){ scanf("%d%d%d", &m, &n, &v); for(int i = 0; i < n; ++i){ int a, b; scanf("%d%d", &a, &b); r[a].push_back(b); } printf("%d\n", bfs()); return 0; } ``` [《滑翔的大象》题目、测试点、标准代码、测试点随机生成工具压缩包](https://www.coco07.com/usr/uploads/2020/08/389662653.zip) © 允许规范转载 赞赏 如果我的文章对你有用，请随意赞赏 赞赏作者 微信
