試題編號：	201409-4
試題名稱：	最優配餐
時間限制：	1.0s
內存限制：	256.0MB
問題描述：	問題描述　　棟棟最近開了一家餐飲連鎖店，提供外賣服務。隨著連鎖店越來越多，怎么合理的給客戶送餐成為了一個急需解決的問題。　　棟棟的連鎖店所在的區域可以看成是一個n×n的方格圖（如下圖所示），方格的格點上的位置上可能包含棟棟的分店（綠色標注）或者客戶（藍色標注），有一些格點是不能經過的（紅色標注）。　　方格圖中的線表示可以行走的道路，相鄰兩個格點的距離為1。棟棟要送餐必須走可以行走的道路，而且不能經過紅色標注的點。　　送餐的主要成本體現在路上所花的時間，每一份餐每走一個單位的距離需要花費1塊錢。每個客戶的需求都可以由棟棟的任意分店配送，每個分店沒有配送總量的限制。　　現在你得到了棟棟的客戶的需求，請問在最優的送餐方式下，送這些餐需要花費多大的成本。輸入格式　　輸入的第一行包含四個整數n, m, k, d，分別表示方格圖的大小、棟棟的分店數量、客戶的數量，以及不能經過的點的數量。　　接下來m行，每行兩個整數xi, yi，表示棟棟的一個分店在方格圖中的橫坐標和縱坐標。　　接下來k行，每行三個整數xi, yi, ci，分別表示每個客戶在方格圖中的橫坐標、縱坐標和訂餐的量。（注意，可能有多個客戶在方格圖中的同一個位置）　　接下來d行，每行兩個整數，分別表示每個不能經過的點的橫坐標和縱坐標。輸出格式　　輸出一個整數，表示最優送餐方式下所需要花費的成本。樣例輸入10 2 3 31 18 81 5 12 3 36 7 21 22 26 8樣例輸出29評測用例規模與約定　　前30%的評測用例滿足：1<=n <=20。　　前60%的評測用例滿足：1<=n<=100。　　所有評測用例都滿足：1<=n<=1000，1<=m, k, d<=n^2。可能有多個客戶在同一個格點上。每個客戶的訂餐量不超過1000，每個客戶所需要的餐都能被送到。

問題鏈接：CCF201609試題。

問題描述：（參照上文）。

問題分析：這是一個求最優問題，通常用BFS（廣度優先搜索）來實現。

程序說明：數組visited[][]中，除了標記訪問過的點之外，不可經過的點和分店也用它來標記，程序邏輯就會變得簡潔。開始時統計訂餐點的數量，以便用作結束條件。不同客戶在同一點時，需要合計他們的訂餐數量。其他都是套路。

提交后得100分的C++語言程序如下：

/* CCF201409-4 最優配餐 */#include <iostream>#include <cstring>#include <queue>using namespace std;const int N = 1000;const int TRUE = 1;const int DIRECTSIZE = 4;struct direct {    int drow, dcol;} direct[DIRECTSIZE] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int buyer[N+1][N+1];int visited[N+1][N+1];struct node {    int row, col, step;    node(){}    node(int r, int c, int s){row=r, col=c, step=s;}};queue<node> q;int buyercount = 0;long long ans = 0;void bfs(int n){    node front, v;    while(!q.empty()) {        front = q.front();        q.pop();        for(int i=0; i<DIRECTSIZE; i++) {            // 移動一格            v.row = front.row + direct[i].drow;            v.col = front.col + direct[i].dcol;            v.step = front.step + 1;            // 行列越界則跳過            if(v.row < 1 || v.row > n || v.col < 1 || v.col > n)                continue;            // 已經訪問過的點不再訪問            if(visited[v.row][v.col])                continue;            // 如果是訂餐點，則計算成本并且累加            if(buyer[v.row][v.col] > 0) {                visited[v.row][v.col] = 1;                ans += buyer[v.row][v.col] * v.step;                if(--buyercount == 0)                    return;            }            // 向前搜索：標記v點為已經訪問過，v點加入隊列中            visited[v.row][v.col] = 1;            q.push(v);        }    }}int main(){    int n, m, k, d, x, y, c;    // 變量初始化    memset(buyer, 0, sizeof(buyer));    memset(visited, 0, sizeof(visited));    // 輸入數據    cin >> n >> m >> k >> d;    for(int i=1; i<=m; i++) {        cin >> x >> y;        q.push(node(x, y, 0));        visited[x][y] = TRUE;      // 各個分店搜索時，需要跳過    }    for(int i=1; i<=k; i++) {        cin >> x >> y;        cin >> c;        if(buyer[x][y] == 0)    // 統計客戶所在地點數量：多個客戶可能在同一地點            buyercount++;        buyer[x][y] += c;       // 統計某個地點的訂單數量    }    for(int i=1; i<=d; i++) {        cin >> x >> y;        visited[x][y] = TRUE;    }    // BFS    bfs(n);    cout << ans << endl;    return 0;}