2013年9月3日

UVa 10389 - Subway

#include <cstdio>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <map>
#define PB push_back
#define MP make_pair
using namespace std;

typedef pair<int, int> P;

struct State {
  State(P p, double need) : p(p), need(need) {}
  bool operator<(const State & other) const {
    return need > other.need;
  }
  P p;
  double need;
};

const double mpm[2] = {10000 / 60.0, 40000 / 60.0};

inline double dis(P & a, P & b) {
  int dx = a.first - b.first, dy = a.second - b.second;
  return sqrt(dx * dx + dy * dy);
}

int main() {
  char temp[9999];
  gets(temp);
  int T;
  sscanf(temp, "%d", &T);
  gets(temp);
  while (T--) {
    gets(temp);
    int sx, sy, ex, ey;
    sscanf(temp, "%d%d%d%d", &sx, &sy, &ex, &ey);
    P s = MP(sx, sy), e = MP(ex, ey);
    vector<P> walk;
    map<P, vector<P> > next;
    walk.PB(e);
    while (gets(temp) && *temp) {
      istringstream ss(temp);
      int x, y;
      vector<P> v;
      while (ss >> x >> y) {
        if (x < 0) {
          break;
        }
        v.PB(MP(x, y));
      }
      for (int i = 0; i < v.size(); i++) {
        walk.PB(v[i]);
        if (i) {
          next[v[i]].PB(v[i - 1]);
        }
        if (i < v.size() - 1) {
          next[v[i]].PB(v[i + 1]);
        }
      }
    }
    priority_queue<State> pq;
    map<P, double> best;
    best[s] = 0;
    pq.push(State(s, 0));
    while (!pq.empty()) {
      P now = pq.top().p;
      double need = pq.top().need;
      pq.pop();
      if (now == e) {
        printf("%.0lf\n", need);
        break;
      }
      for (int i = 0; i < walk.size(); i++) {
        P & j = walk[i];
        if (now != j) {
          double nextNeed = need + dis(now, j) / mpm[0];
          if (best.find(j) == best.end() || nextNeed < best[j]) {
            pq.push(State(j, nextNeed));
            best[j] = nextNeed;
          }
        }
      }
      for (int i = 0; i < next[now].size(); i++) {
        P & j = next[now][i];
        if (now != j) {
          double nextNeed = need + dis(now, j) / mpm[1];
          if (best.find(j) == best.end() || nextNeed < best[j]) {
            pq.push(State(j, nextNeed));
            best[j] = nextNeed;
          }
        }
      }
    }
    if (T) {
      puts("");
    }
  }
  return 0;
}

沒有留言:

張貼留言