求助,雷雨RE了6个点
  • 板块灌水区
  • 楼主zero2005
  • 当前回复10
  • 已保存回复10
  • 发布时间2020/9/21 21:01
  • 上次更新2023/11/5 12:49:20
查看原帖
求助,雷雨RE了6个点
182260
zero2005楼主2020/9/21 21:01
#include<bits/stdc++.h>
using namespace std;
int w[1001][1001];
long long d[4][1000010];
int num[1001][1001];
int n,m;int a,b,c;
int v[1001000];
const int mx=10001;
vector<int>ver[mx];
vector<int>edge[mx];
struct rec
{
	int x,y;
}rt[1000001];
void add(int x,int y,int z)
{
	ver[x].push_back(y);
	edge[x].push_back(z);
}
priority_queue< pair< int, int> >q;
void flyd()
{
	int m=n*n;
	for(int k=1;k<=m;k++)
    for(int i=1;i<=m;i++)
    for(int j=1;j<=m;j++)
    {
    	d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	}
}
void dj(int s,int res)
{
	memset(v,0,sizeof(v));
	d[res][s]=0;
	q.push(make_pair(0,s));
	while(q.size())
	{
		int x=q.top().second;q.pop();
		if(v[x])continue;
		v[x]=1;
		for(int i=0;i<ver[x].size();i++)
		{
			int y=ver[x][i];
			if(v[y])continue;
			int z=edge[x][i];
			if(d[res][y]>d[res][x]+z)
			{
				d[res][y]=d[res][x]+z;
				q.push(make_pair(-d[res][y],y)); 
			}
		}
	}
}
int main()
{
	cin>>n>>m>>a>>b>>c;
	memset(w,0x3f,sizeof(w));
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		cin>>w[i][j];		
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		num[i][j]=(i-1)*m+j;
		rt[(i-1)*m+j].x=i;
		rt[(i-1)*m+j].y=j;
		
	}
   for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(i!=1){
            	add((i-1)*m+j,(i-2)*m+j,w[i-1][j]);
            }
            if(i!=n)add((i-1)*m+j,i*m+j,w[i+1][j]);
            if(j!=1)add((i-1)*m+j,(i-1)*m+j-1,w[i][j-1]);
            if(j!=n)add((i-1)*m+j,(i-1)*m+j+1,w[i][j+1]);
        }
   memset(d,0x7f,sizeof(d));
long long ans=1e9;
dj(a,1);
dj((n-1)*m+b,2);
dj((n-1)*m+c,3);
for(int i=1;i<=n*m;i++)
{
	int xx=a;
	int yy=(n-1)*m+b;
	int zz=(n-1)*m+c;
	int cnt=d[1][i]+d[2][i]+d[3][i]+w[1][a]+w[n][b]+w[n][c]-2*w[rt[i].x][rt[i].y];
	if(cnt<ans)
	{
		ans=cnt;
	}
}
cout<<ans;
	return 0;
}
2020/9/21 21:01
加载中...