CSP 201409-4 最优配餐 bfs 多源

配餐 bfs 多源"/>

CSP 201409-4 最优配餐 bfs 多源

• 题目：

n*n的网格，m个分店，k个客户，d堵墙。可以从任意分店给任意客户配餐，每一份餐走一单位距离花费为1，求最小花费。

• 思路：

最短路径，多起点多终点，可以将所有起点看作一个整体，所有起点一次性放入队列。

int vis[][]记录每个点的信息，-2代表墙，0代表没有到达过但可以到达，>0代表订餐数。bool in[][]记录是否到达过。int dis[][]记录到达每一个顶点的最短路径长度。ans累加耗费。

初始化：所有起点标记到达，距离为0。客户>0，墙标记-2。

将所有起点放入队列，取点，判断是否为客户，若是，ans累加dis(距离)*vis(订餐数)。继续向外扩展，遍历四个相邻位置，对于符合条件的（1.没有到达边界 2.没有到达过 3.不是墙），标记到达，距离加1，入队列。

• 注意：

1.每个坐标位置可能有多个客户，在输入客户信息（a,b,c）分别代表客户x坐标、客户y坐标、订餐数量时，不能直接赋值，要用+=

2.最终结果ans需要用long long 保存

3.不能将in[][]合并进vis[][]:

若合并，假设vis=-1代表到达过，在扩展入队列过程中，某点符合条件，若该点有客户，不能直接标记为-1（这样会导致丢失该点的订餐数，而该点的耗费还没有计入ans），只能选择从队列中取出该点时才能将其标记为-1。这样将导致在这个时间间隔中，该点可能再次被访问。

但是可以把in[][]与dis[][]合并在一起，也可以把dis去掉，在结构体Point中增加cost表示该点耗费。

• 代码

• #include<iostream>
  #include<cstdio>
  #include<queue>
  #include<cstring>
  using namespace std;
  //二维平面上的点 
  struct Point{int x;int y;
  };
  const int maxn=1e3+5;
  int vis[maxn][maxn];//0代表没到过但可以到，-2代表墙 ，>0代表客户数 
  int dis[maxn][maxn];//记录最小距离 
  bool in[maxn][maxn];//标记是否到达过 
  int dx[]{0,0,-1,1};
  int dy[]{1,-1,0,0};
  int n,m,k,d;int main(){cin>>n>>m>>k>>d;queue<Point> q;memset(vis,0,sizeof(vis));//初始化为0memset(dis,0,sizeof(vis)); long long ans=0;//保存最终结果 int a,b,c;//输入连锁店 while(m--){cin>>a>>b;q.push({a,b});//将所有起点压入栈中in[a][b]=true;//到过 }  //输入客户 while(k--){cin>>a>>b>>c;vis[a][b]+=c;//同一位置可能有多个客户 }//输入墙while(d--){cin>>a>>b;vis[a][b]=-2;}while(!q.empty()){Point now=q.front(); q.pop();//特判终点if(vis[now.x][now.y]>0){//有客户 ans+=vis[now.x][now.y]*dis[now.x][now.y];} //向外扩展for(int i=0;i<4;i++){int x=now.x+dx[i],y=now.y+dy[i];//特判 1.没有到达边界 2.没有到达过 3.不是墙 if(x>=1&&x<=n&&y>=1&&y<=n&&!in[x][y]&&vis[x][y]>=0){in[x][y]=true;dis[x][y]=dis[now.x][now.y]+1;q.push({x,y});} } }cout<<ans<<endl;return 0;
  }