The Hare and the Hounds (UVa Live Archive World Finals 2008 Banff)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=42&page=show_problem&problem=2122
実装：50分　デバッグ：30分

問題

めんどくさいので略。YUHAのACM-ICPC 2007-2009総集編を参照。

解法

英語を読んで、シュミレートするだけ。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

typedef int Weight;
struct Edge {
  int index;
  int src;
  int dest;
  int fangle;
  int tangle;
  Weight weight;
  int confirm;
  Edge() {;}
  Edge(int index, int src, int dest, int fangle, int tangle, Weight weight) : index(index), src(src), dest(dest), fangle(fangle), tangle(tangle), weight(weight), confirm(0x0f0f0f0f) {;}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void PrintMatrix(const Matrix &matrix) {
  for (int y = 0; y < (int)matrix.size(); y++) {
    for (int x = 0; x < (int)matrix[y].size(); x++) {
      printf("%d ", matrix[y][x]);
    }
    puts("");
  }
}

int n, e, m, D, start, end, sdir;
bool choicePoint[1000];
Graph g;
int hareAns;
int houndAns;
vector<int> route;

bool Calc(const Edge &e, bool search, int rest);
bool Move(const Edge &e, bool search, int rest) {
  bool ret = true;
  if (search) {
    int d = min(e.weight, rest);
    bool nsearch = e.confirm > d;
    if (!nsearch) { d = e.weight; rest = 1 << 28; }
    bool ok = true;
    if (d == e.weight) {
      ok &= Calc(e, nsearch, rest - d);
    } else {
      ok = false;
    }
    if (!ok) {
      houndAns += d * 2;
      ret = false;
    } else {
      assert(d == e.weight);
      hareAns += d;
      houndAns += d;
      route.push_back(e.index);
    }
  } else {
    Calc(e, search, 1 << 28);
    hareAns += e.weight;
    houndAns += e.weight;
    route.push_back(e.index);
  }
  return ret;
}

Edge MainRoadRule(int angle, const vector<Edge> &es) {
  assert(es.size() > 0);
  angle = 180 + angle;
  if (angle >= 360) { angle -= 360; }
  int best = 1000;
  int index = -1;
  REP(i, es.size()) {
    int v = es[i].fangle - angle;
    if (v > 180) { v -= 360; }
    if (v < -180) { v += 360; }
    if (abs(v) < abs(best) ||
        (abs(v) == abs(best) && v > 0)) {
      best = v;
      index = i;
    }
  }
  return es[index];
}

bool Calc(const Edge &e, bool search, int rest) {
  int from = e.dest;
  if (search && (rest == 0 || choicePoint[from] || g[from].size() == 1)) { return false; }
  if (!search && end == from) { return true; }

  bool ret = true;
  if (choicePoint[from]) {
    Edge prev = e;
    prev.fangle = prev.tangle;
    vector<Edge> es = g[from];
    while (true) {
      FORIT(it, es) {
        if (prev.index == it->index) { es.erase(it); break; }
      }
      Edge next = MainRoadRule(prev.fangle, es);
      if (Move(next, true, D)) { break; }
      prev = next;
    }
  } else {
    Edge next = MainRoadRule(e.tangle, g[from]);
    ret = Move(next, search, rest);
  }
  return ret;
}

int main() {
  int test_case = 0;
  while (scanf("%d %d %d %d %d %d %d", &n, &e, &m, &D, &start, &end, &sdir), n|e|m|D|start|end|sdir) {
    test_case++;
    start--; end--;
    MEMSET(choicePoint, false);
    g = Graph(1000);
    hareAns = 0;
    houndAns = 0;
    route.clear();

    REP(i, n) {
      int v;
      scanf("%d", &v);
      choicePoint[v - 1] = true;
    }
    Edge startE;
    REP(i, e) {
      int f, t, fdir, tdir, d;
      scanf("%d %d %d %d %d", &f, &t, &fdir, &tdir, &d);
      f--; t--;
      g[f].push_back(Edge(i, f, t, fdir, tdir, d));
      g[t].push_back(Edge(i, t, f, tdir, fdir, d));
      if (f == start && sdir == fdir) { startE = g[f].back(); }
      if (t == start && sdir == tdir) { startE = g[t].back(); }
    }
    REP(i, m) {
      int f, r, d;
      scanf("%d %d %d", &f, &r, &d);
      f--; r--;
      REP(i, 1000) {
        FORIT(it, g[i]) {
          if (it->index != r) { continue; }
          if (it->src == f) { it->confirm = min(it->confirm, d); }
          else { it->confirm = min(it->confirm, it->weight - d); }
        }
      }
    }
    Move(startE, false, 1 << 28);
    reverse(route.begin(), route.end());
    printf("Case %d:\n", test_case);
    printf("   Length of hare's route is %d\n", hareAns);
    printf("   Length of hound's search is %d\n", houndAns);
    printf("   Route:");
    FORIT(it, route) { printf(" %d", *it + 1); }
    printf("\n\n");
  }
}