SRM 642 Div2 1000 TallShoes

問題概要
n個の都市が道路ネットワークで結ばれている。
王様は、都市0から都市n-1まで移動したい。
各道路には高さが設定されており、その値以下の高さの靴を履いている場合のみ、道路を通行することができる。
王様はできるだけ高い靴を履いて移動したい。
移動を開始する前に王様は各道路の高さを上げることができる。道路の高さをx上げるためにはx*xのコストがかかる。予算が与えられるので、移動時に使用できる靴の高さの最大値を求めよ。

解法
靴の高さで二分探索。
靴の高さが決まれば、ノード=都市、エッジのコスト=(靴の高さ - 道路の高さ)^2のようにしてグラフを構築できる。あとは構築したグラフでダイクストラすればいい。
ドワンゴのコンテストでも「二分探索 + ダイクストラ」の問題が出たけど、この組み合わせは面白い。

実装

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

const long long oo = 1LL<<60;
vector<pair<int, int> > g[50];
long long d[50];

class TallShoes {
  long long calc(long long h, long long l) {
    if (h >= l) return 0;
    return (l-h) * (l-h);
  }
  
  long long dijkstra(int s, int t, int l) {
    typedef pair<long long, int> PLI;
    priority_queue<PLI, vector<PLI>, greater<PLI> > Q;
    fill(d, d+50, oo);
    Q.push({0, 0});
    d[0] = 0;
    while (!Q.empty()) {
      long long v;
      int p;
      tie(v, p) = Q.top();
      Q.pop();
      if (d[p] != v)
        continue;
      for (auto &e: g[p]) {
        int q;
        int h;
        tie(q, h) = e;
        long long tmp = d[p] + calc(h, l);
        if (tmp < d[q]) {
          Q.push({tmp, q});
          d[q] = tmp;
        }
      }
    }
    return d[t];
  }

  void init(vector<int> xs, vector<int> ys, vector<int> hs) {
    REP (i, 50) g[i].clear();
    int sz = xs.size();
    REP (i, sz) {
      g[xs[i]].push_back({ys[i], hs[i]});
      g[ys[i]].push_back({xs[i], hs[i]});
    }
  }
  
public:
  int maxHeight(int N, vector<int> X, vector<int> Y, vector<int> height, long long B) {
    init(X, Y, height);
    int hi = 1<<28;
    int lo = 0;
    while (hi - lo > 1) {
      int mi = (hi + lo) / 2;
      if (dijkstra(0, N-1, mi) <= B)
        lo = mi;
      else
        hi = mi;
    }
    return lo;
  }
};