配餐 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; }
更多推荐
CSP 201409-4 最优配餐 bfs 多源
发布评论