201409-4 ccf--最优配餐

分手后的思念是犯贱 2022-05-15 06:42 136阅读 0赞

题目链接：  
[最优配餐][Link 1]

题目大意：  
中文题目，很清晰了，不解释

解题思路：  
这题根据题目大意即刻想到需要用bfs()客户离最近餐厅的距离，然后乘以数量就是答案！  
bfs的思路，是这样的，先把餐厅坐标入队列，并且步数为0，然后每次取出队首元素，进行上下左右四个方向扩展，对没有遍历过且不是障碍点加入队尾，这样当我们访问到客户点时，就是最短路径，记录下访问了几位客户，当全部客户点都访问完，返回此时答案！  
算是简单题，但是还是需要多思考！！！

AC代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    
    
    using namespace std;
    
    int n,m,k,d;
    
    struct node{
        int x,y;
        int step;
        node(){}
        node(int _x, int _y, int s):x(_x),y(_y),step(s){}
    };
    
    queue<node> q;
    int map[1005][1005],vis[1005][1005];
    
    int dre[4][2] = {
       {-1,0},{
       1,0},{
       0,-1},{
       0,1}};
    long long bfs(){
        long long ans = 0;
        int cnt = 0;
        while(!q.empty()){
            node tmp =q.front();
            q.pop();
            for(int i=0; i<4; ++i){
                int tx = tmp.x+dre[i][0];
                int ty = tmp.y+dre[i][1];
                if(vis[tx][ty]||tx<=0||tx>n||ty<=0||ty>n) continue;
                vis[tx][ty] = 1;
                if(map[tx][ty]){
                    ans += (map[tx][ty]*(tmp.step+1));
                    cnt++;
                    if(cnt>=k) return ans;
                }
                q.push(node(tx,ty,tmp.step+1));
            }
        //  cout<<"23333"<<endl;
        }
    }
    
    int main(){
        memset(map, 0, sizeof(map));
        memset(vis, 0, sizeof(vis));
        cin>>n>>m>>k>>d;
        for(int i=0; i<m; ++i){
            int x,y;
            cin>>x>>y;
            q.push(node(x,y,0));
        }
        for(int i=0; i<k; ++i){
            int x,y,c;
            cin>>x>>y>>c;
            map[x][y]=c;
        }
        for(int i=0; i<d; ++i){
            int x,y;
            cin>>x>>y;
            vis[x][y] = 1;
        }
        cout<<bfs()<<endl;
        return 0；
    }

[Link 1]: http://118.190.20.162/view.page?gpid=T13