@[cbkxx](/user/705343)
你这打的什么堆
by Paradise_Lost @ 2024-01-05 21:40:59
优先队列打错了吧
by wizard（偷开O2 @ 2024-01-05 21:47:19
@[Paradise_Lost](/user/688649) 错了模板怎么过的
by cbkxx @ 2024-01-05 21:49:10
@[cbkxx](/user/705343)
小孩子不懂事，问着玩
x和y可以等于0x3f3f3f3f3f3f3f吗？
删空栈时可以up吗？
by Paradise_Lost @ 2024-01-05 21:53:16
@[Paradise_Lost](/user/688649) 1.可以=0x3f3f3f3f
2.我发现top没请0，改完结果没变
by cbkxx @ 2024-01-05 21:57:20
@[Paradise_Lost](/user/688649) 我刚学堆，如有错误，请指出
by cbkxx @ 2024-01-05 21:58:42
@[cbkxx](/user/705343)
过了
by Paradise_Lost @ 2024-01-05 22:09:43
@[cbkxx](/user/705343)
极值开大，heap开小点就过了
by Paradise_Lost @ 2024-01-05 22:10:39
```cpp
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y;
};
struct n2{
int x,y;
long long ro;
}heap[1000005];
int n,m,a,b,c,f[1005][1005],top;
long long dis[3][1005][1005],ans=1e18;
bool vis[1005][1005];
vector<node>g[1005][1005];
void Hinsert(n2 x){
heap[++top]=x;
int k=top;
while(k!=1){
if(heap[k].ro<heap[k/2].ro)swap(heap[k],heap[k/2]);
else break;
k/=2;
}
}
void Herase(){
swap(heap[1],heap[top]);
heap[top].x=heap[top].y=0;heap[top].ro=0x3f3f3f3f3f3f3f3f;
top--;
int k=1;
while(heap[k].ro>heap[k*2].ro||heap[k].ro>heap[k*2+1].ro&&k*2+1<=top){
if(heap[k*2].ro<heap[k*2+1].ro){
swap(heap[k],heap[k*2]);
k*=2;
}else{
swap(heap[k],heap[k*2+1]);
k=k*2+1;
}
}
}
void dij(int k,int sx,int sy){
for(int i=0;i<=1000000;i++)heap[i].x=heap[i].y=0,heap[i].ro=0x3f3f3f3f3f3f3f3f;
dis[k][sx][sy]=f[sx][sy];
memset(vis,0,sizeof(vis));
vis[sx][sy]=1;
int dx=sx,dy=sy;
Hinsert({dx,dy,f[sx][sy]});
for(int i=1;i<n*m;i++){
for(int j=0,px,py;j<g[dx][dy].size();j++){
px=g[dx][dy][j].x,py=g[dx][dy][j].y;
if(dis[k][px][py]>dis[k][dx][dy]+f[px][py]){
dis[k][px][py]=dis[k][dx][dy]+f[px][py];
Hinsert({px,py,dis[k][px][py]});
}
}
dx=heap[1].x;
dy=heap[1].y;
Herase();
vis[dx][dy]=1;
}
}
int main(){
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>>f[i][j];
if(i!=1)g[i][j].push_back({i-1,j});
if(i!=n)g[i][j].push_back({i+1,j});
if(j!=1)g[i][j].push_back({i,j-1});
if(j!=m)g[i][j].push_back({i,j+1});
}
}
dij(0,1,a);
dij(1,n,b);
dij(2,n,c);
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]-f[i][j]*2);
}
}
cout<<ans;
return 0;
}
```
写的比较丑，所以空间常数大了一点，至于RE是赋值的问题
by Paradise_Lost @ 2024-01-05 22:11:37
@[Paradise_Lost](/user/688649) 谢谢
by cbkxx @ 2024-01-05 22:15:24