萌新,刚学,妹子,求救QWQ
查看原帖
萌新,刚学,妹子,求救QWQ
469811
JUY_zss楼主2021/10/20 18:33

5 6 9 三个点WA了,自己看不出来了,求救QWQ

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
long long int n,m,a,b,c,r[1005][1005],xl[15]={0,-1,1,0,0},yl[15]={0,0,0,-1,1},ansl=1e15,d[15][1005][1005];
bool vis[1005][1005];
typedef pair<long long int,long long int>qq;
typedef pair<long long int,qq>pp;
priority_queue<pp,vector<pp>,greater<pp> >q;
int main()
{
	cin>>n>>m>>a>>b>>c;
	for (long long int i=1;i<=n;i++)
	for (long long int j=1;j<=m;j++)
	cin>>r[i][j];
	for (long long int k=1;k<=3;k++)
	for (long long int i=1;i<=n;i++)
	for (long long int j=1;j<=m;j++)
	d[k][i][j]=1e9;
	d[1][1][a]=r[1][a];
	q.push(pp{r[1][a],qq{1,a}});
	while (!q.empty())
	{
		pp uu=q.top();
		q.pop();
		long long int xx=uu.second.first,yy=uu.second.second;
		if (vis[xx][yy])
		continue;
		vis[xx][yy]=1;
		for (int i=1;i<=4;i++)
		{
			long long int xxl=xx+xl[i],yyl=yy+yl[i];
			if (xxl<1 || yyl<1 || xxl>n || yyl>m)
			continue;
			if (d[1][xxl][yyl]>d[1][xx][yy]+r[xxl][yyl])
			{
				d[1][xxl][yyl]=d[1][xx][yy]+r[xxl][yyl];
				q.push(pp{d[1][xxl][yyl],qq{xxl,yyl}});
			}
		}
	}
	for (long long int i=1;i<=n;i++)
	for (long long int j=1;j<=m;j++)
	vis[i][j]=0;
	d[2][n][b]=r[n][b];
	q.push(pp{r[n][b],qq{n,b}});
	while (!q.empty())
	{
		pp uu=q.top();
		q.pop();
		long long int xx=uu.second.first,yy=uu.second.second;
		if (vis[xx][yy])
		continue;
		vis[xx][yy]=1;
		for (int i=1;i<=4;i++)
		{
			long long int xxl=xx+xl[i],yyl=yy+yl[i];
			if (xxl<1 || yyl<1 || xxl>n || yyl>m)
			continue;
			if (d[2][xxl][yyl]>d[2][xx][yy]+r[xxl][yyl])
			{
				d[2][xxl][yyl]=d[2][xx][yy]+r[xxl][yyl];
				q.push(pp{d[2][xxl][yyl],qq{xxl,yyl}});
			}
		}
	}
	for (long long int i=1;i<=n;i++)
	for (long long int j=1;j<=m;j++)
	vis[i][j]=0;
	d[3][n][c]=r[n][c];
	q.push(pp{r[n][c],qq{n,c}});
	while (!q.empty())
	{
		pp uu=q.top();
		q.pop();
		long long int xx=uu.second.first,yy=uu.second.second;
		if (vis[xx][yy])
		continue;
		vis[xx][yy]=1;
		for (int i=1;i<=4;i++)
		{
			long long int xxl=xx+xl[i],yyl=yy+yl[i];
			if (xxl<1 || yyl<1 || xxl>n || yyl>m)
			continue;
			if (d[3][xxl][yyl]>d[3][xx][yy]+r[xxl][yyl])
			{
				d[3][xxl][yyl]=d[3][xx][yy]+r[xxl][yyl];
				q.push(pp{d[3][xxl][yyl],qq{xxl,yyl}});
			}
		}
	}
	for (long long int i=1;i<=n;i++)
	for (long long int j=1;j<=m;j++)
	ansl=min(ansl,(d[1][i][j]+d[2][i][j]+d[3][i][j]-r[i][j]*2));
	cout<<ansl;
	return 0;
}
2021/10/20 18:33
加载中...