送外卖

反向建边，vis记录每条边起点是否在途中，起点从0开始搜索，若按a的路径能走通则走a，反之走b

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
vector<int>edge[100001];
bool vis[100001];
int a[100001],b[100001];
char ans[100001];
bool f;
int n;
void dfs(int x){
	if (vis[x])  
	   return ;
	vis[x]=true;
	for (int i=0;i<edge[x].size();i++)
	   dfs(edge[x][i]);
	return; 
}


void dfs2(int x,int step){
	if (x<0||x>=n||!vis[x])
	 return;
	 if (step>=n)
	   return;
    if (x==n-1)
      {
      	f=true;
      	return;
	  }
	  if (x+a[x]>=0&&x+a[x]<n&&vis[x+a[x]])
	    {
	    	ans[step]='a';
	    	dfs2(x+a[x],step+1);
		}
       else {
       	ans[step]='b';
       	dfs2(x+b[x],step+1);
	   }
  return;
} 

int main(){
  scanf("%d",&n);
  for (int i=0;i<n;i++)
     scanf("%d",&a[i]);
	   
  for (int i=0;i<n;i++)
     scanf("%d",&b[i]);
	
   for(int i=0;i<n;i++)
    if(i+a[i]>=0&&i+a[i]<n)
	    edge[i+a[i]].push_back(i); 
  
    for(int i=0;i<n;i++)
    if (i+b[i]>=0&&i+b[i]<n)
        edge[i+b[i]].push_back(i);
        
    dfs(n-1);
    if (!vis[0])
      printf("No solution!\n");
    else {
    	dfs2(0,0);
        if(f)
		 printf("%s\n",ans);
		else printf("Infinity!\n"); 
	}
  return 0;
}