最优配餐

参考

参考代码

多源 BFS 的学习

思路

分析可知，这道题用多源 BFS 算法。

1. 将每个分店视作 “源” ，从各个源开始 BFS 扩展
2. 对于某个源的每次试图在四个方向的扩展，判断其是否越界，如果没有越界。试图更新其最小花费时间 t ，如果更新成功将之入队。

在多源 BFS 视频讲解中，董老师将源比作洪水源头十分形象，每秒扩展一步，先到哪个点，哪个点就确定最短距离，这里就相当于每个源头同步扩展，如同洪水同步淹没，谁先到到哪个点，那么其将确定最短距离。

注意

1. 队列要开 $N^2$ 空间
2. res 要开 long long

代码

#include<iostream>
#include<cstring>
using namespace std;
const int N=1010;
int g[N][N];
int t[N][N];
int n,m,k,d;
int client[N*N][3];
typedef pair<int,int>PII;
PII q[N*N];
int hh=0,tt=-1;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
bool check(int a,int b){
    return (a>=1 and a<=n and b>=1 and b<=n and (g[a][b]!=-1));
}
void bfs(){
    while(hh<=tt){
        auto start=q[hh++];
        int x=start.first,y=start.second;

        for(int i=0;i<4;i++){
            int x1=x+dx[i],y1=y+dy[i];
            if(check(x1,y1)){
                //cout<<"yes"<<endl;
                if(t[x1][y1]>t[x][y]+1){
                    //cout<<"renew";
                    t[x1][y1]=t[x][y]+1;// 这里第二个写成了t[x1][y]+1 
                    q[++tt]={x1,y1};//找到更短距离，并入队 
                }
            }
        }

    }
}
int main(){
    ios::sync_with_stdio(false);
    memset(t,0x3f,sizeof t);
    memset(g,0,sizeof g);
    cin>>n>>m>>k>>d;
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        q[++tt]={a,b};
        t[a][b]=0;
    }
    for(int i=0;i<k;i++){
        cin>>client[i][0]>>client[i][1]>>client[i][2];
    }

    for(int i=0;i<d;i++){
        int a,b;
        cin>>a>>b;
        g[a][b]=-1;
    }
    bfs();
//  for(int i=1;i<=n;i++){
//      for(int j=1;j<=n;j++){
//          cout<<t[i][j]<<" ";
//      }
//      cout<<endl;
//  } 
//  cout<<endl;
    int res=0;
    for(int i=0;i<k;i++){
        res+=(t[client[i][0]][client[i][1]])*client[i][2];
    }
    cout<<res;
}