Codeforces Round #101 (Div. 2) D - Take-off Ramps

http://codeforces.com/contest/141/problem/D

概要

X 軸に沿って x = 0 から x = L までスキーをする．

通常は単位時間あたりに単位距離進むことができる．

途中には n 個の傾斜がある． i 番目の傾斜は位置 x[i] にあり，その p[i] 手前から加速して x[i] から d[i] の距離を t[i] の時間でジャンプすることができる． ただし，加速中も単位時間あたりに単位距離進むとみなす．

+x 方向だけでなく，-x 方向に進んでも構わない． ただし，傾斜からのジャンプは +x 方向にしかできない． また，x < 0 や x < L の地点に行くことはできない．

ゴールまでの最短時間と，そのときに使った傾斜を答える．

制約

解法

スタート，ゴール，加速開始地点，ジャンプの着地地点 だけを考えてダイクストラ．

経路復元が若干面倒．

  1 #include <iostream>
  2 #include <vector>
  3 #include <map>
  4 #include <queue>
  5 #include <algorithm>
  6 using namespace std;
  7 
  8 struct ramp { int id, x, d, t, p; };
  9 struct edge
 10 {
 11   int id, to;
 12   long long cost;
 13   edge(int i, int t, long long c) : id(i), to(t), cost(c) {}
 14   bool operator<(const edge& e) const { return cost > e.cost; }
 15 };
 16 
 17 int main()
 18 {
 19   ios::sync_with_stdio(false);
 20   int N, L;
 21   cin >> N >> L;
 22   vector<ramp> rs;
 23   vector<int> xs;
 24   for (int i = 0; i < N; i++) {
 25     ramp r;
 26     r.id = i+1;
 27     cin >> r.x >> r.d >> r.t >> r.p;
 28     if (r.x-r.p >= 0 && r.t < r.d) {
 29       rs.push_back(r);
 30       xs.push_back(r.x - r.p);
 31       xs.push_back(r.x + r.d);
 32     }
 33   }
 34   xs.push_back(0);
 35   xs.push_back(L);
 36   sort(xs.begin(), xs.end());
 37   xs.erase(unique(xs.begin(), xs.end()), xs.end());
 38   const int M = xs.size();
 39 
 40   vector<vector<edge> > g(M);
 41   map<int,int> x_inv;
 42   for (int i = 0; i < M; i++) {
 43     x_inv[xs[i]] = i;
 44   }
 45   for (int i = 0; i < M-1; i++) {
 46     g[i].push_back(edge(-1, i+1, xs[i+1] - xs[i]));
 47     g[i+1].push_back(edge(-1, i, xs[i+1] - xs[i]));
 48   }
 49   for (vector<ramp>::const_iterator it = rs.begin(); it != rs.end(); ++it) {
 50     if (!x_inv.count(it->x - it->p) || !x_inv.count(it->x + it->d)) {
 51       throw "x_inv";
 52     }
 53     const int u = x_inv[it->x - it->p];
 54     const int v = x_inv[it->x + it->d];
 55     g[u].push_back(edge(it->id, v, it->p + it->t));
 56   }
 57 
 58   vector<long long> dist(M, 1LL<<40);
 59   priority_queue<pair<long long,int> > q;
 60   dist[0] = 0;
 61   q.push(make_pair(0, 0));
 62 
 63   vector<pair<int,int> > pre(M);
 64   pre[0].second = -1;
 65   while (!q.empty()) {
 66     const int n = q.top().second;
 67     const long long c = -q.top().first;
 68     q.pop();
 69     if (n == M-1) {
 70       break;
 71     }
 72     if (dist[n] < c) {
 73       continue;
 74     }
 75     for (vector<edge>::const_iterator it = g[n].begin(); it != g[n].end(); ++it) {
 76       const int m = it->to;
 77       const long long cc = c + it->cost;
 78       if (cc < dist[m]) {
 79         dist[m] = cc;
 80         pre[m] = make_pair(it->id, n);
 81         q.push(make_pair(-cc, m));
 82       }
 83     }
 84   }
 85   cout << dist[M-1] << endl;
 86   vector<int> t;
 87   for (int n = M-1; n != -1; n = pre[n].second) {
 88     const int id = pre[n].first;
 89     if (id > 0) {
 90       t.push_back(id);
 91     }
 92   }
 93   cout << t.size() << endl;
 94   for (vector<int>::const_reverse_iterator it = t.rbegin(); it != t.rend(); ++it) {
 95     if (it != t.rbegin()) {
 96       cout << ' ';
 97     }
 98     cout << *it;
 99   }
100   cout << endl;
101   return 0;
102 }
codeforces/141d.cc