AOJ 2050 - Dig or Climb

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2050

概要

図のように n 個の点からなる折れ線で表現された地形が与えられる．

移動するとき，

の2通りの方法が可能である．

このとき，スタート地点からゴール地点までに要する最小の時間を答える．

制約

解法

穴を掘って進むとしたら，n 個の点のうちのいずれかから掘り始めるか，いずれかへ掘り進む場合に限る．

各点から左右に穴を掘った場合のノードとエッジを追加してから，ダイクストラすればいい．

  1 #include <cstdio>
  2 #include <vector>
  3 #include <queue>
  4 #include <complex>
  5 using namespace std;
  6 typedef complex<double> P;
  7 static const double EPS = 1e-6;
  8 inline double cross(const P& a, const P& b) { return a.real()*b.imag() - b.real()*a.imag(); }
  9 
 10 struct line/*{{{*/
 11 {
 12   P a, b;
 13   line() {}
 14   line(const P& p, const P& q) : a(p), b(q) {}
 15 };/*}}}*/
 16 
 17 struct segment/*{{{*/
 18 {
 19   P a, b;
 20   segment() {}
 21   segment(const P& x, const P& y) : a(x), b(y) {}
 22 
 23   inline bool intersects(const line& ln) const
 24   {
 25     return cross(ln.b - ln.a, a - ln.a) * cross(ln.b - ln.a, b - ln.a) < EPS;
 26   }
 27 
 28   inline P intersection(const line& ln) const
 29   {
 30     const P x = b - a;
 31     const P y = ln.b - ln.a;
 32     return a + x*(cross(y, ln.a - a))/cross(y, x);
 33   }
 34 };/*}}}*/
 35 
 36 int main()
 37 {
 38   int N;
 39   while (scanf("%d", &N) != EOF && N != 0) {
 40     int vw, vc;
 41     scanf("%d %d", &vw, &vc);
 42     vector<P> ps;
 43     for (int i = 0; i < N; i++) {
 44       int x, y;
 45       scanf("%d %d", &x, &y);
 46       ps.push_back(P(x, y));
 47     }
 48 
 49     vector<vector<pair<int,double> > > g(3*N);
 50     for (int i = 0; i < N-1; i++) {
 51       g[3*i].push_back(make_pair(3*(i+1), abs(ps[i+1] - ps[i])/vw));
 52     }
 53     for (int i = 0; i < N; i++) {
 54       if (i > 0 && ps[i-1].imag() > ps[i].imag()) {
 55         // left edge
 56         const line ln(ps[i], ps[i] + P(1, 0));
 57         for (int j = i-2; j >= 0; j--) {
 58           const segment s(ps[j], ps[j+1]);
 59           if (s.intersects(ln)) {
 60             const P p = s.intersection(ln);
 61             const int n = 3*i+1;
 62             g[3*j].push_back(make_pair(n, abs(p - ps[j])/vw));
 63             g[n].push_back(make_pair(3*i, abs(ps[i] - p)/vc));
 64             break;
 65           }
 66         }
 67       }
 68       if (i < N-1 && ps[i].imag() < ps[i+1].imag()) {
 69         // right edge
 70         const line ln(ps[i], ps[i] + P(1, 0));
 71         for (int j = i+1; j < N-1; j++) {
 72           const segment s(ps[j], ps[j+1]);
 73           if (s.intersects(ln)) {
 74             const P p = s.intersection(ln);
 75             const int n = 3*i+2;
 76             g[3*i].push_back(make_pair(n, abs(p - ps[i])/vc));
 77             g[n].push_back(make_pair(3*(j+1), abs(ps[j+1] - p)/vw));
 78             break;
 79           }
 80         }
 81       }
 82     }
 83 
 84     static const double INF = 1e10;
 85     vector<double> dist(3*N, INF);
 86     dist[0] = 0;
 87     priority_queue<pair<double,int> > q;
 88     q.push(make_pair(0, 0));
 89     while (!q.empty()) {
 90       const double c = -q.top().first;
 91       const int n = q.top().second;
 92       q.pop();
 93       if (n == 3*(N-1)) {
 94         printf("%.6f\n", c);
 95         break;
 96       }
 97       if (c > dist[n]) {
 98         continue;
 99       }
100       for (vector<pair<int,double> >::const_iterator it = g[n].begin(); it != g[n].end(); ++it) {
101         const int m = it->first;
102         const double cc = c + it->second;
103         if (cc < dist[m]) {
104           dist[m] = cc;
105           q.push(make_pair(-cc, m));
106         }
107       }
108     }
109   }
110   return 0;
111 }
aoj/2050.cc