Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-08

SRM451 div2 (過去問)

23:35

Hard - PizzaDelivery

地図と, ピザ屋の位置と, ピザの配達先が与えられる. ピザ屋には二人の配達員がいる. すべてのピザを配り終える最短時間を計算する.

アルゴリズムは大きく2つのフェーズに分かれます. ひとつは各配達先への最短経路の計算, もうひとつは二人の配達員への配達先の割り振りの決定です. まず最短経路について, 各配達先について, ダイクストラ法で最短距離を計算しています. 次に割り振りについて, 配達先が高々20, その配達先それぞれを2人の配達員どちらかに割り振るので, すべての割り振り方は2^20=1048576通りです. 全探索で間に合いそうです. ある割り振り方の際の時間の計算方法は, 配達員Aの配達先までの時間をT1, T2 ... Tm (T1 <= T2 <= ... <= Tm) とすると, T1*2 + T2*2 + ... + Tm となります. 両方の配達員についてこれを計算し, 大きい方がこの割り振り方の時間です.

以下のコードですが, システムテストが通りませんでした. どうも最短経路を計算している部分にバグがあるようです.

class PizzaDelivery {
public:
  vector <string> terrain;
  int startx, starty;

  vector <int> make_node(int cost, int x, int y) {
    vector <int> node(3, 0);
    node[0] = cost, node[1] = x, node[2] = y;
    return node;
  }

  bool canMove(int fromx, int fromy, int tox, int toy) {
    if (0 <= fromx && fromx < terrain.size() && 0 <= fromy && fromy < terrain[0].size() &&
        0 <= tox && tox < terrain.size() && 0 <= toy && toy < terrain[0].size())
      if ((terrain[fromx][fromy] == 'X' || terrain[fromx][fromy] == '$' || terrain[tox][toy] == 'X' || terrain[tox][toy] == '$') ||
          (abs(terrain[fromx][fromy] - terrain[tox][toy]) < 2))
        return true;
    return false;
  }

  int findRoute(int x, int y) {
    int ret = -1;
    priority_queue <vector <int>, vector <vector <int> >, greater <vector <int> > > q;
    int visited[terrain.size()][terrain[0].size()];
    int dirx[4] = {0, 1, 0, -1};
    int diry[4] = {1, 0, -1, 0};

    for (int i=0; i<terrain.size(); i++)
      for (int j=0; j<terrain[0].size(); j++)
        visited[i][j] = INT_MAX;
    visited[startx][starty] = 0;
    q.push(make_node(0, startx, starty));

    while (!q.empty()) {
      vector <int> cur = q.top();
      q.pop();

      if (cur[1] == x && cur[2] == y) {
        ret = cur[0];
        break;
      }

      for (int i=0; i<4; i++) {
        int nextx = cur[1] + dirx[i];
        int nexty = cur[2] + diry[i];
        int next_cost = 0;

        if (canMove(cur[1], cur[2], nextx, nexty)) {
          if (terrain[cur[1]][cur[2]] == 'X' || terrain[cur[1]][cur[2]] == '$' || terrain[nextx][nexty] == 'X' || terrain[nextx][nexty] == '$')
            next_cost = cur[0] + 2;
          else if (abs(terrain[cur[1]][cur[2]] - terrain[nextx][nexty]) == 0)
            next_cost = cur[0] + 1;
          else if (abs(terrain[cur[1]][cur[2]] - terrain[nextx][nexty]) == 1)
            next_cost = cur[0] + 3;
          else
            continue;

          if (visited[nextx][nexty] == INT_MAX)
            q.push(make_node(next_cost, nextx, nexty));
        
          visited[nextx][nexty] = min(visited[nextx][nexty], next_cost);
        }
      }
    }

    return ret;
  }

  int deliverAll(vector <string> _terrain) {
    terrain = _terrain;
    vector <vector <int> > buildings;
    vector <int> costs;
    int ret = INT_MAX;

    for (int i=0; i<terrain.size(); i++)
      for (int j=0; j<terrain[0].size(); j++)
        if (terrain[i][j] == 'X') {
          startx = i, starty = j;
        } else if (terrain[i][j] == '$') {
          vector <int> tmp(2, 0);
          tmp[0] = i, tmp[1] = j;
          buildings.push_back(tmp);
        }

    for (int i=0; i<buildings.size(); i++) {
      int res = findRoute(buildings[i][0], buildings[i][1]);
      if (res == -1) return -1;
      costs.push_back(res);
    }

    for (int i=0; i<(1 << buildings.size()); i++) {
      int cost_1 = 0, cost_2 = 0;
      int max_1 = 0, max_2 = 0;
      for (int j=0; j<buildings.size(); j++)
        if (i & (1 << j)) {
          cost_1 += costs[j] * 2;
          max_1 = max(max_1, costs[j]);
        } else {
          cost_2 += costs[j] * 2;
          max_2 = max(max_2, costs[j]);
        }

      cost_1 -= max_1, cost_2 -= max_2;

      ret = min(ret, max(cost_1, cost_2));
    }

    return ret;
  }
};