求助,为啥#1就挂了
查看原帖
求助,为啥#1就挂了
525375
Richard_Whr楼主2023/9/11 19:25
/*
*/
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=55,M=210,E=N*M*3;
int h[N][M],ne[E],w[E],idx;
PII e[E];
bool has[N][M][2];
int n,m;
int t[N];
int dist[N][M];
bool st[N][N];

void add(PII a,PII b,int c)
{
	e[idx]=b,ne[idx]=h[a.x][a.y],w[idx]=c,h[a.x][a.y]=idx++;
}

int bfs(PII S,PII T)
{
	memset(dist,0x3f,sizeof dist);
	memset(st,0,sizeof st);
	dist[S.x][S.y]=0;
	st[S.x][S.y]=true;
	deque<PII> q;
	q.push_back(S);
	
	while(q.size())
	{
		auto t=q.front();
		q.pop_front();
		
		if(t.x==T.x&&t.y==T.y) return dist[t.x][t.y];
		for(int i=h[t.x][t.y];~i;i=ne[i])
		{
			auto j=e[i];
			if(st[j.x][j.y]) continue;
			else
			{
				st[j.x][j.y]=true;
				dist[j.x][j.y]=dist[t.x][t.y]+w[i];
				if(w[i]==1) q.push_back(j);
				else q.push_front(j);
			}
		}
	}
	
	return -1;
}

int main()
{
	int T=0;
	while(scanf("%d",&n),n)
	{
		T++;
		memset(h,-1,sizeof h),idx=0;
		memset(has,0,sizeof has);
		scanf("%d",&m);
		for(int i=1;i<n;i++) scanf("%d",&t[i]);
		int m1,m2;
		scanf("%d",&m1);
		for(int i=1;i<=m1;i++)
		{
			int x;
			scanf("%d",&x);
			int last=x;
			for(int j=1;j<=n;j++)
			{ 
				if(last<=m) has[j][last][0]=true;
				//else break;
				last+=t[j];
			}
		}
		scanf("%d",&m2);
		for(int i=1;i<=m2;i++)
		{
			int x;
			scanf("%d",&x);	
			int last=x;
			for(int j=n;j>=1;j--)
			{
				
				if(last<=m) has[j][last][1]=true;
				//else break;
				last+=t[j-1];
			}
		}	
		
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(j+1<=m) add({i,j},{i,j+1},1);
				if(has[i][j][0]) add({i,j},{i+1,j+t[i]},0);
				if(has[i][j][1]) add({i,j},{i-1,j+t[i-1]},0); 
			}
		}
		
		int res=bfs({1,0},{n,m});
		if(res==-1) printf("Case Number %d: impossible\n",T);
		else printf("Case Number %d: %d\n",T,res);
	}	
	
	return 0;
} 
2023/9/11 19:25
加载中...