RT根本没听说过这个RE是什么(本蒟蒻只知道RE数组越界和除以0)
代码(貌似有小bug,但不知道为啥RE):
#include<bits/stdc++.h>
using namespace std;
const int N=1001;
const long long INF=1e18;
int n,m;
int zip(int i,int j)
{
return (i-1)*m+j;
}
struct edge
{
int from,to;
long long w;
edge(int a,int b,long long c)
{
from=a;to=b;w=c;
}
};
vector<edge>mp[N];
struct node
{
int id;long long dis;
node(int b,long long c)
{
id=b;
dis=c;
}
bool operator <(const node &b) const
{
return dis>b.dis;
}
};
long long om[N][N],dp[5][N*N];
bool vis[N*N];
void dijkstra(int cs,int s)
{
memset(vis,false,sizeof(vis));
dp[cs][s]=0;
priority_queue<node>q;
q.push(node(s,dp[cs][s]));
while(!q.empty())
{
node k=q.top();q.pop();
if(vis[k.id]) continue;
vis[k.id]=true;
for(int i=0;i<mp[k.id].size();i++)
{
edge y=mp[k.id][i];
if(vis[y.to]) continue;
if(dp[cs][y.to]>y.w+k.dis)
{
dp[cs][y.to]=y.w+k.dis;
q.push(node(y.to,dp[cs][y.to]));
}
}
}
}
int main()
{
int a,b,c;
cin>>n>>m>>a>>b>>c;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>om[i][j];
if(i>1)
{
int k1=zip(i,j),k2=zip(i-1,j);
mp[k1].push_back(edge(k1,k2,om[i-1][j]));
mp[k2].push_back(edge(k2,k1,om[i][j]));
}
if(j>1)
{
int k1=zip(i,j),k2=zip(i,j-1);
mp[k1].push_back(edge(k1,k2,om[i][j-1]));
mp[k2].push_back(edge(k2,k1,om[i][j]));
}
}
}
memset(dp,0x3f,sizeof(dp));
dijkstra(0,zip(1,a));
dijkstra(1,zip(n,b));
dijkstra(2,zip(n,c));
long long ans=INF;
int kk=om[1][a]+om[n][b]+om[n][c];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
int k1=zip(i,j);
ans=min(ans,kk+dp[0][k1]+dp[1][k1]+dp[2][k1]-2*om[i][j]);
}
}
cout<<ans<<endl;
return 0;
}
验证码fwaw(a)祭