dfs即可,代码有注释. #include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],b[N],st[N],vis[N],flag=0,n;
char ans[N];
//确认过眼神是一个难难的题目H
展开全文
送外卖
思路(反向建图+bfs)
注意本题所求的是最小字典序的字符串，而不是最小长度的字符串，所以需要反向建图，求出state[i]=truestate[i]=truestate[i]=true表示点iii可以到达点nnn(反向建图的bfs1函数中结点编号1-n，求最小字典序的bfs函数中结点编号
展开全文
比题解1更简单易懂的DFS
前言：一开始我不明白什么时候输出infinity，然后去看了题解1的代码，发现使用了dfs+回溯，其中的逻辑并不是特别容易理解。但是通过阅读那个题解我明白了什么时候需要输出infinity，下面讲解思路
输出infinity的条件：相信很多卡在这道题的选手都是对这一点有
展开全文
解题思路：如果用bfs从下标为0每次移动至另一状态判断是否能到达终点，其实现难点在于如何判断是否会Infinity，因为不同的走法其路线不同走过的顶点也不同；用dfs+回溯可以AC ；用bfs求解思路：反向建图，从下标n-1(实现时下标从1-n)判断是否有到达0的路径，在经过的节点上标记。接着从下标
展开全文
这道题其实考察的知识点不难，甚至可以说是简单，就dfs完事.
但是坑就坑在这个"Infinity!"上,因为题干没有给出合适的测试用例,导致我理解错了题意！
不知道你们对输出"Infinity!"的条件的理解是什么,我最开始理解成只需要满足"最小字典序"和"无限长(即有环存在)"就应该打印出"Inf
展开全文
这道题用深搜可以，广搜也行
先找到所以可达的点，反向建图即可
然后从起点扩展，注意是字典序最短，而不是路径最短
在扩展的过程中，如果点没走过并且可达则加入队列，这个时候就可以直接break掉了
因为对于当前可达的点来说一定可达
是按照字典序走的
如果发现某个点的扩展点是遍历过的并且是可达的，那么存在
展开全文
建议复制到编译器更好食用。（使用dfs，即深度优先搜索）
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
