求助,T了4个点,其他都AC
查看原帖
求助,T了4个点,其他都AC
303105
haiming楼主2024/8/1 22:20

这是原程序,调了好久,真的不知道怎么改了

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,x,y,z,k,h[1000000],a[200000],b[200000],f[600][600],xx,yy,cnt,head[1000000],vis[1000000],i,j,v;
int tag[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
struct node{int x,y;}p[2000000];
struct note{int nex,to;long long dis;}g[2000000];
void read(int &x){
	int f=0;char ch=getchar();x=0;
	while(ch>'9'||ch<'0'){if(ch=='-')f=1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
	if(f)x=-x;
}
void add(int u,int v,long long w){g[++cnt].nex=head[u];g[cnt].to=v;g[cnt].dis=w;head[u]=cnt;}
int id(int x,int y){return x*(m+1)+y;}
void sc(int o){
	int x,i;
	h[o]=0;vis[o]=1;h[o]=0;
	queue<int>p;
	p.push(o);
	while(!p.empty()){
		x=p.front();p.pop();vis[x]=0;
		for(i=head[x];i;i=g[i].nex){
			if(h[g[i].to]>h[x]+g[i].dis){
				h[g[i].to]=h[x]+g[i].dis;
				if(!vis[g[i].to]){
					vis[g[i].to]=1;
					p.push(g[i].to);
				}
			}
		}
	}
}
void dfs(){
	int t=0,w=0,x,y,xx,yy;
	memset(f,127,sizeof(f));
	for(int i=1;i<=k;i++) p[++w].x=a[i],p[w].y=b[i],f[a[i]][b[i]]=0;
	t=1;
	while(t<=w){
		x=p[t].x;y=p[t].y;
		for(int i=0;i<4;i++){
			xx=x+tag[i][0];yy=y+tag[i][1];
			if(xx<0||xx>n||yy<0||yy>m||f[xx][yy]<=f[x][y]+1)continue;
			f[xx][yy]=f[x][y]+1;
			p[++w].x=xx;p[w].y=yy;
		}
		t++;
	}
}
#undef int
int main(){
	read(n);read(m);read(x);read(y);read(z);
	memset(h,127,sizeof(h));
	read(k);
	for(i=1;i<=k;i++)read(a[i]),read(b[i]);
	dfs();
	for(i=0;i<=n;i++)
		for(j=0;j<=m;j++){
			for(v=0;v<4;v++){
				xx=i+tag[v][0];yy=j+tag[v][1];
				if(xx<0||xx>n||yy<0||yy>m)continue;
				add(id(i,j),id(xx,yy),z);
			}
			add(id(i,j),id(i,j)+(n+1)*(m+1),y);
			add(id(i,j),id(i,j)+2*(n+1)*(m+1),y);
			
			for(v=0;v<2;v++){
				xx=i+tag[v][0];yy=j+tag[v][1];
				if(xx<0||xx>n||yy<0||yy>m)continue;
				add(id(i,j)+(n+1)*(m+1),id(xx,yy)+(n+1)*(m+1),x);
			}
			add(id(i,j)+(n+1)*(m+1),id(i,j),f[i][j]*z);
			
			for(v=2;v<4;v++){
				xx=i+tag[v][0];yy=j+tag[v][1];
				if(xx<0||xx>n||yy<0||yy>m)continue;
				add(id(i,j)+2*(n+1)*(m+1),id(xx,yy)+2*(n+1)*(m+1),x);
			}
			add(id(i,j)+2*(n+1)*(m+1),id(i,j),f[i][j]*z);
		}
	sc(id(a[1],b[1]));
	printf("%lld",h[id(a[k],b[k])]);
	return 0;
}
2024/8/1 22:20
加载中...