CCF 最优配餐 100分

谁借莪１个温暖的怀抱￠ 2023-07-25 14:29 16阅读 0赞

题目传送门：[http://118.190.20.162/view.page?gpid=T13][http_118.190.20.162_view.page_gpid_T13]

思路：多源BFS

#include<bits/stdc++.h>
    #include<iostream>
    #include<algorithm>
    #include<string>
    #include<vector>
    #include<queue>
    #include<set>
    using namespace std;
    const int MAXN = 1002; 
    const int INF = 999999;
    
    struct Coord{
    	int x,y;
    	long long step;
    	Coord(int x,int y,long long step){
    		this->x = x;
    		this->y = y;
    		this->step = step;
    	}
    };
    int graph[MAXN][MAXN];
    queue<Coord> coords;   
    bool vis[MAXN][MAXN];
    long long totalCost = 0;
    int n;
    
    inline void initData(){
    	for(int i=0;i<=n;i++){
    		for(int j=0;j<=n;j++){
    			graph[i][j] = 0;  //交点 
    		}
    	}
    }
    
    bool judge(int x,int y){
    	if(x<1 || y<1 || x>n || y>n){
    		return false;
    	}
    	if(vis[x][y]){
    		return false;
    	}
    	if(graph[x][y] == -2){
    		vis[x][y] = true;
    		return false;
    	} 
    	return true;
    }
    
    void BFS(){
    	int dir[4][2] = {
       {0,1},{1,0},{0,-1},{-1,0}};
    	while(!coords.empty()){
    		Coord coord = coords.front();
    		coords.pop();
    		for(int i=0;i<4;i++){
    			int nx = coord.x + dir[i][0];
    			int ny = coord.y + dir[i][1];
    			long long step = coord.step + 1;
    			if(judge(nx,ny)){
    				if(graph[nx][ny] > 0){  //是客户所在地 
    					int cost = graph[nx][ny] * step; //计算送餐成本 
    					totalCost += cost; 
    				}
    				coords.push(Coord(nx,ny,step));
    				vis[nx][ny] = true;
    			}
    		}
    	}
    } 
    
    int main(){
    	int m,k,d;
    	int x,y,w;
    	cin>>n>>m>>k>>d;
    	initData();
    	for(int i=1;i<=m;i++){ //输入店铺所在的点 
    		cin>>x>>y;
    		coords.push(Coord(x,y,0)); 
    		vis[x][y] = true;
    	}
    	for(int i=1;i<=k;i++){ //输入客户所在的点 
    		cin>>x>>y>>w;
    		graph[x][y] += w;  //w(w>0)---表示订餐数量是w。 
    	} 
    	for(int i=1;i<=d;i++){ //输入不能走的点 
    		cin>>x>>y;
    		vis[x][y] = true;  
    	} 
    	BFS();
    	cout<<totalCost<<endl;
    	return 0;
    }

[http_118.190.20.162_view.page_gpid_T13]: http://118.190.20.162/view.page?gpid=T13