时间复杂度 $\mathcal{O}(nm\log(nm)+nm)$

#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;
            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;
}