改了下,不MLE了,但是WA两个点![](//图.tk/7)
```
#include<bits/stdc++.h>
using namespace std;
const int N=1001;
const long long INF=1e10;
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*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[N*N];
long long ans[N*N];
bool vis[N*N];
priority_queue<node>q;
void dijkstra(int s)
{
memset(dp,0x3f,sizeof dp);
memset(vis,false,sizeof(vis));
dp[s]=0;
q.push(node(s,dp[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[y.to]>y.w+k.dis)
{
dp[y.to]=y.w+k.dis;
q.push(node(y.to,dp[y.to]));
}
}
}
}
void work()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
int k=zip(i,j);
ans[k]+=dp[k];
}
}
}
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(zip(1,a));
work();
dijkstra(zip(n,b));
work();
dijkstra(zip(n,c));
work();
long long fans=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);
int k2=kk+ans[k1]-2*om[i][j];
if(i==1&&j==a) k2-=om[1][a];
else if(i==n&&j==b)k2-=om[n][b];
else if(i==n&&j==c)k2-=om[n][c];
fans=min(fans,kk+ans[k1]-2*om[i][j]);
}
}
cout<<fans<<endl;
return 0;
}
```
by kk1501201 @ 2023-08-20 08:59:42