跳格子

一、题目

二、解法

这道题不需要字符串的$dijkstra$dijkstra，我们先找出能跑到$n$n的点，可以通过建反向边再跑$bfs$bfs完成。
然后根据这个去$dfs$dfs，我们先选$a$a操作，跑到被染色的点就直接继续$dfs$dfs，否则尝试$b$b操作，如果有一个点被两次访问到，那就说明进入了循环节，输出$Infinity!$Infinity!。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 100005;
int read()
{
    int num=0,flag=1;char c;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
    while(c>='0'&&c<='9')num=(num<<3)+(num<<1)+(c^48),c=getchar();
    return num*flag;
}
int n,to,tot,a[MAXN],b[MAXN],vis[MAXN],pd[MAXN],f[MAXN];
string ans;
queue<int> q;
struct edge
{
	int v,next;
}e[MAXN*2];
void add_edge(int u,int v) //建反边
{
	e[++tot]=edge{u,f[v]},f[v]=tot;
} 
void bfs()
{
	q.push(n);
	vis[n]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=f[u];i;i=e[i].next)
		{
			int v=e[i].v;
			if(!vis[v])
			{
				vis[v]=1;
				q.push(v);
			}
		}
	}
}
void dfs(int x)
{
	if(x==n) return ;
	if(pd[x])
	{
		puts("Infinity!");
		exit(0);
	}
	pd[x]=1;
	to=x+a[x];
	if(1<=to && to<=n && vis[to])
	{
		ans+='a';
		dfs(to);
		return ;
	}
	to=x+b[x];
	if(1<=to && to<=n && vis[to])
	{
		ans+='b';
		dfs(to);
	}
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		if(1<=i+a[i] && i+a[i]<=n)
			add_edge(i,i+a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		b[i]=read();
		if(1<=i+b[i] && i+b[i]<=n)
			add_edge(i,i+b[i]);
	}
	bfs();
	if(!vis[1])
	{
		puts("No solution!");
		return 0;
	}
	dfs(1);
	cout<<ans<<endl;
}