求大佬看看,全部wa了,不知为什么
查看原帖
求大佬看看,全部wa了,不知为什么
363495
我爱杨帆楼主2020/9/25 22:08
#include<bits/stdc++.h>
using namespace std;
struct node
{
	int v,w;
	
};
struct node1
{
	int id;
	int di;
	bool operator <(const node1 &x) const
	{
		return di>x.di;
	}
};
int w1[5]={0,0,1,-1};
int w2[5]={1,-1,0,0};
bool vis[1010025];
priority_queue<node1> q;
vector<node>a[1010025];
int dis[1001000];
void dij(int s)
{
	dis[s]=0;
	q.push((node1){s,0});
	while(!q.empty())
	{
	  node1 t=q.top();
	  q.pop();
	  int now=t.id,d=dis[now];	
	  if(vis[now])
	  continue;
	  vis[now]=1;
	  for(int i=0;i<a[now].size();i++)
	   { 
         if(vis[a[now][i].v])
		 continue;
		 if(d+a[now][i].w<dis[a[now][i].v])
		 {
		  dis[a[now][i].v]=d+a[now][i].w;
		  q.push((node1){a[now][i].v,dis[a[now][i].v]});	
		 }	   	
	   }	
	}
}
void recover()
{
	memset(vis,0,sizeof(vis));
	while(!q.empty())
	q.pop();
	memset(dis,0x3f3f,sizeof(dis));
}
int read()
{
	char c=getchar();
	int r=0;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9')
	{
	 r=r*10+c-'0';
	 c=getchar();
	}
	return r;
}
int ans[10005][10005],r[10005][10005],num[10005][10005];
int main()
{   
    int tot=0;
    int n=read(),m=read(),a1=read(),b1=read(),c1=read();
	for(int i=n;i>=1;i--)
	 for(int j=1;j<=m;j++)
	  {
	  r[i][j]=read();
	  tot++;
	  num[i][j]=tot;
      }
    for(int i=1;i<=tot;i++)
     dis[i]=0x3f3f;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
      for(int k=0;k<=3;k++)
       { 
       	if(i+w1[k]<=0||i+w1[k]>n)
       	continue;
       	if(j+w2[k]<=0||j+w2[k]>m)
       	continue;
       	int p=i+w1[k],q=j+w2[k];
       	a[num[i][j]].push_back((node){num[p][q],r[p][q]});
	   }
	 dij(num[n][a1]);
	 for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	   ans[i][j]+=dis[num[i][j]];
	 recover();
	 dij(num[1][b1]);
	 for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	   ans[i][j]+=dis[num[i][j]];
	 recover();
	  dij(num[1][c1]);
	 for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	   ans[i][j]+=dis[num[i][j]];
	 recover();
	 int anss=0x3f3f;
	 for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	   {
	   anss=min(anss,ans[i][j]);
       }
	 cout<<anss;          
} 
2020/9/25 22:08
加载中...