传送门
解题思路
分别从a、b、c三个点求单源最短路。
然后枚举两条道路相交的节点(i,j),因为是点权,所以答案为 \(dis[0][i][j]+dis[1][i][j]+dis[2][i][j]+e[i][j]\)。
注意用set进行的堆优化,要防止set丢失元素,所以要对pair的第二维(存点的坐标)的结构体进行合理的重载运算符。
虽然没有固定的顺序,但是因为pair和set的原因,需要重载运算符。
例如重载'<',如果直接return a.x<b.x,会导致吞掉dis和横坐标相等的点(因为假设a,b横坐标相等,则a<b返回false,b<a也返回false)。
而当我们改为return a.x<=b.x,则不会出现问题。依旧假设a,b横坐标相等,则a<b返回true,b<a也返回true。
就因为这个东西调了一上午。。。
AC代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
const int maxn=1005;
int n,m,a,b,c;
long long dis[3][maxn][maxn],e[maxn][maxn],ans=1e18;
struct node{
int x,y;
node(int x,int y):x(x),y(y){}
friend bool operator <(node a,node b){
return a.x<=b.x;
}
};
node s(0,0);
void dij(int id){
set<pair<long long,node> > q;
dis[id][s.x][s.y]=0;
q.insert(make_pair(0,s));
while(!q.empty()){
node u=q.begin()->second;
q.erase(q.begin());
if(u.x>1&&dis[id][u.x-1][u.y]>dis[id][u.x][u.y]+e[u.x][u.y]){
node to(u.x-1,u.y);
q.erase(make_pair(dis[id][u.x-1][u.y],to));
dis[id][u.x-1][u.y]=dis[id][u.x][u.y]+e[u.x][u.y];
q.insert(make_pair(dis[id][u.x-1][u.y],to));
}
if(u.y>1&&dis[id][u.x][u.y-1]>dis[id][u.x][u.y]+e[u.x][u.y]){
node to(u.x,u.y-1);
q.erase(make_pair(dis[id][u.x][u.y-1],to));
dis[id][u.x][u.y-1]=dis[id][u.x][u.y]+e[u.x][u.y];
q.insert(make_pair(dis[id][u.x][u.y-1],to));
}
if(u.x<n&&dis[id][u.x+1][u.y]>dis[id][u.x][u.y]+e[u.x][u.y]){
node to(u.x+1,u.y);
q.erase(make_pair(dis[id][u.x+1][u.y],to));
dis[id][u.x+1][u.y]=dis[id][u.x][u.y]+e[u.x][u.y];
q.insert(make_pair(dis[id][u.x+1][u.y],to));
}
if(u.y<m&&dis[id][u.x][u.y+1]>dis[id][u.x][u.y]+e[u.x][u.y]){
node to(u.x,u.y+1);
q.erase(make_pair(dis[id][u.x][u.y+1],to));
dis[id][u.x][u.y+1]=dis[id][u.x][u.y]+e[u.x][u.y];
q.insert(make_pair(dis[id][u.x][u.y+1],to));
}
}
}
int main(){
ios::sync_with_stdio(false);
memset(dis,0x3f,sizeof(dis));
cin>>n>>m>>a>>b>>c;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>e[i][j];
}
}
s.x=1;
s.y=a;
dij(0);
s.x=n;
s.y=b;
dij(1);
s.y=c;
dij(2);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans=min(ans,dis[0][i][j]+dis[1][i][j]+dis[2][i][j]+e[i][j]);
}
}
cout<<ans;
return 0;
}