P6833 SPFA 20tps 求调 玄关
查看原帖
P6833 SPFA 20tps 求调 玄关
1054021
114_Hzh_AK_NOIP_514楼主2024/8/10 09:01
#include <bits/stdc++.h>
using namespace std;
struct node
{
	int x,y,z;
}t;
queue <node> q;
int n,m,a,b,c;
int mapp[1005][1005];
int dis[1005][1005][5];
int zong[1005][1005];
bool book[1005][1005][5];
int d[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
void SPFA(int x,int y,int z)
{
	while(!q.empty())
	{
		q.pop();
	}
	dis[x][y][z]=mapp[x][y];
	book[x][y][z]=1;
	q.push({x,y,z});
	while(!q.empty())
	{
		t=q.front();
		book[t.x][t.y][t.z]=0;
		q.pop();
		for(int i=0;i<4;i++)
		{
			int nx=t.x+d[i][0];
			int ny=t.y+d[i][1];
			int nz=t.z;
			if(nx>n || nx<1 || ny>m || ny<1) continue;
			if(mapp[nx][ny]+dis[t.x][t.y][t.z]<dis[nx][ny][nz])
			{
				dis[nx][ny][nz]=mapp[nx][ny]+dis[t.x][t.y][t.z];
				if(book[nx][ny][nz]==0)
				{
					book[nx][ny][nz]=1;
					q.push({nx,ny,nz});
				}
			}
		}
	}
}
int main()
{
	cin >> n >> m >> a >> b >> c;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin >> mapp[i][j];
		}
	}
	memset(dis,0x3f,sizeof dis);
	memset(book,0,sizeof book);
	SPFA(1,a,1);
	SPFA(n,b,2);
	SPFA(n,c,3);
	int minn=0x3f3f3f3f;
	for(int k=1;k<=3;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				zong[i][j]+=dis[i][j][k];
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			zong[i][j]-=2*mapp[i][j];
			minn=min(zong[i][j],minn);
		}
		
	}
	cout << minn;
	return 0;
}
2024/8/10 09:01
加载中...