过全部点代码~

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

#define x first
#define y second

using namespace std;
const int N = 1010,INF = 0x3f3f3f3f;
typedef pair<int,int> PII;
typedef long long LL;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
vector<PII> st,cm;
LL w[N],ans[N][N];
int g[N][N],d[N][N];
queue<PII> q;
int n,m,k,dd;

void bfs(){
    while(q.size()){
        auto p = q.front();
        q.pop();
        int dis = d[p.x][p.y];
        for(int k = 0;k < 4;k++){
            int tx = p.x + dx[k],ty = p.y + dy[k];
            if(tx >= 1 && tx <= n && ty >= 1 && ty <= n && !g[tx][ty]){
                if(d[tx][ty] > dis + 1){
                    d[tx][ty] = dis + 1;
                    q.push({tx,ty});
                }
            }
        }
    }

}

int main(){
    ios::sync_with_stdio(false);//输入量较大，此语句可以加快输出
    cin >> n >> m >> k >> dd;
    memset(d,0x3f,sizeof d);
    for(int i = 0;i < m;i++){
        int x,y;
        cin >> x >> y ;
        st.push_back({x,y});
        q.push({x,y});
        d[x][y] = 0;
    }

    for(int i = 0;i < k;i++){
        int x,y,c;
        cin >> x >> y >> c;
        cm.push_back({x,y});
        w[i] = c;
    }
    for(int i = 0;i < dd;i++){
        int x,y;
        cin >> x >> y;
        g[x][y] = 1;
    }

    bfs();
    LL res = 0;
    for(int i = 0;i < k;i++){
        auto xx = cm[i];
        int val = w[i];
        res += d[xx.x][xx.y] * val;
    }

    cout << res << endl;

    return 0;
}

只能过n较小的点

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

#define x first
#define y second

using namespace std;
const int N = 1010,INF = 0x3f3f3f3f;
typedef pair<int,int> PII;
typedef long long LL;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
vector<PII> st,cm;
LL w[N],ans[N][N];
int g[N][N],d[N][N];

int n,m,k,dd;

int bfs(){
    memset(ans,0x3f,sizeof ans);
    LL res = 0;
    for(int i = 0;i < k;i++){
        auto temp = cm[i];
        // cout << temp.x << ' ' << temp.y << endl;
        LL val = w[i];
        for(int j = 0;j < m;j++){
            auto t = st[j];
            memset(d,-1,sizeof d);
            queue<PII> q;
            q.push(t);
            d[t.x][t.y] = 0;
            while(q.size()){
                auto p = q.front();
                q.pop();
                int dis = d[p.x][p.y];

                // cout << p.x << ' ' << p.y << endl;
                if(p.x == temp.x && p.y == temp.y){
                    ans[p.x][p.y] = min(ans[p.x][p.y],dis * val);
                    break;
                }
                for(int k = 0;k < 4;k++){
                    int tx = p.x + dx[k],ty = p.y + dy[k];
                    if(tx >= 1 && tx <= n && ty >= 1 && ty <= n && d[tx][ty] == -1 && !g[tx][ty]){
                        d[tx][ty] = dis + 1;
                        q.push({tx,ty});
                    }
                }
            }
        }
        res += ans[temp.x][temp.y];
    }

    return res;
}

int main(){
    cin >> n >> m >> k >> dd;
    for(int i = 0;i < m;i++){
        int x,y;
        cin >> x >> y ;
        st.push_back({x,y});
    }

    for(int i = 0;i < k;i++){
        int x,y,c;
        cin >> x >> y >> c;
        cm.push_back({x,y});
        w[i] = c;
    }
    for(int i = 0;i < dd;i++){
        int x,y;
        cin >> x >> y;
        g[x][y] = 1;
    }

    cout << bfs() << endl
    return 0;
}