@[rickyxrc](/user/387961) @[caiest_oier](/user/932169) @[itshawn](/user/401479) @[like_doggy](/user/389737) @[Zi_Gao](/user/554698)
by 刘辰雨 @ 2023-08-25 16:03:41
@[__immccn123__](/user/385633)
by 刘辰雨 @ 2023-08-25 16:04:55
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <bitset>
#include <vector>
#include <cstring>
using namespace std;
typedef long long i64;
void read(int &xt) {
char ch=getchar(); int x=0,w=1;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); xt = x*w;
}
vector<int> vec[1000006];
int v[1000006];
bitset<1000006> vist;
int n, m, a, b, c;
priority_queue<pair<i64, int>, vector<pair<i64, int> >, greater<pair<i64, int> > > q;
i64 dis[3][1000006];
void dijkstra(int root, int type) {
for(int i = 1 ; i <= n ; i++) {
for(int j = 1 ; j<= m ; j++) {
dis[type][1000*(i-1)+j-1] = 0x3f3f3f3f3f3f3f3f;
}
}
dis[type][root] = v[root];
while(!q.empty()) q.pop();
for(int i = 1 ; i<= n ; i++) {
for(int j = 1 ; j<= m ; j++) {
vist[1000*(i-1)+j-1] = false;
}
}
q.push({dis[type][root], root});
while(!q.empty()) {
int now = q.top().second;
q.pop();
if(vist[now]) continue;
vist[now] = true;
for(int tmp : vec[now]) {
if(vist[tmp]) continue;
if(dis[type][now] + v[tmp]<dis[type][tmp]){
dis[type][tmp] = min(dis[type][tmp], dis[type][now] + v[tmp]);
q.push({dis[type][tmp], tmp});
}
}
}
}
i64 ans = 1e18;
int main() {
read(n); read(m); read(a); read(b); read(c);
for(int i = 1 ; i<= n ; i++) {
for(int j = 1 ; j <= m ; j++) {
int c = 1000*(i-1)+j-1;
read(v[c]);
if(i != 1) vec[c].push_back(c-1000), vec[c-1000].push_back(c);
if(j != 1) vec[c].push_back(c-1), vec[c-1].push_back(c);
if(i != n) vec[c].push_back(c+1000), vec[c+1000].push_back(c);
if(j != m) vec[c].push_back(c+1), vec[c+1].push_back(c);
}
}
dijkstra(a-1, 0);
dijkstra(1000*(n-1)+b-1, 1);
dijkstra(1000*(n-1)+c-1, 2);
for(int i = 1 ; i<= n ; i++) {
for(int j = 1 ; j <= m ; j++) {
int c = (i-1)*1000+j-1;
ans = min(ans , dis[0][c]+dis[1][c]+dis[2][c]-2*v[c]);
}
}
printf("%lld\n", ans);
return 0;
}
```
by Zi_Gao @ 2023-08-25 16:10:10
@[刘辰雨](/user/524906) 你这个 dij 有点小问题。有松弛才放进去
by Zi_Gao @ 2023-08-25 16:11:40
但是这个好像是常数优化，本身时间复杂度没问题
by Zi_Gao @ 2023-08-25 16:13:04
膜拜
by LuckiestShawn @ 2023-08-25 16:14:49
@[Zi_Gao](/user/554698) 拜谢
by 刘辰雨 @ 2023-08-27 00:45:56