Benelux Algorithm Programming Contest 2016 E Charles in Charge

問題

N個の頂点と、M個の重み付きの辺があるグラフが与えられます。
頂点1から頂点Nに行く最短経路に、X%加えた新しい距離以内で、頂点1から頂点Nにたどる道の中で辺の重みの最大値が、最も小さくなるときの、辺の重みの最大値を求めなさい、というものです。

解法

まずは素直にダイクストラ法を利用して最短経路を求めます。
その後、X%加えた新しい距離を出します。これをXとします。
今回求めるのは辺の重みの最大値を最小化したものになるので、二分探索を利用します。
現在見ている値をDとしたとき、

• 辺の重みがD以下のもののみを使用して、X以内に頂点1から頂点Nにたどり着くことができるか

という判定方法を利用して二分探索をします。
最終的に残ったDが答えになります。
やっていることはすごくシンプルなダイクストラ法と、ときどき見かける二分探索の組み合わせになります。最近二分探索をちょくちょく書いていたので、バグ無しで通すことができました。うれしいです。

提出コードは以下になります。

#include <bits/stdc++.h>
#define inf 1000000000000000000
using namespace std;

long long memo[10005] = {0};
vector<pair<long long, long long>> edge[10005];
long long n, m, x, minn, maxd = 0;
long long c1, c2, t;
priority_queue<pair<long long, long long>,
               vector<pair<long long, long long>>,
               greater<pair<long long, long long>>>
    pq;

void dk(long long d);
long long solve();

int main() {
  int i;
  cin >> n >> m >> x;
  for(i = 0; i < m; ++i) {
    cin >> c1 >> c2 >> t;
    --c1;
    --c2;
    edge[c1].push_back(make_pair(t, c2));
    edge[c2].push_back(make_pair(t, c1));
    maxd = max(maxd, t);
  }
  dk(inf);
  minn = memo[n - 1] * (double)(1 + 0.01 * x);
  cout << solve() << endl;
  return 0;
}

void dk(long long d) {
  long long nd, np;
  pair<long long, long long> now, nextn;
  memo[0] = 0;
  for(int i = 1; i < n; ++i) memo[i] = inf;
  pq.push(make_pair(0, 0));
  while(pq.size() > 0) {
    now = pq.top();
    pq.pop();
    nd = now.first;
    np = now.second;
    for(int i = 0; i < edge[np].size(); ++i)
      if(edge[np][i].first <= d) {
        nextn = make_pair(edge[np][i].first + nd,
                          edge[np][i].second);
        if(nextn.first < memo[nextn.second]) {
          memo[nextn.second] = nextn.first;
          pq.push(nextn);
        }
      }
  }
}

long long solve() {
  long long l = 0, r = maxd, now;
  while(r - l > 0) {
    now = (l + r) / 2;
    if(r - l == 1) {
      dk(l);
      if(memo[n - 1] <= minn)
        now = l;
      else
        now = r;
      break;
    }
    dk(now);
    if(memo[n - 1] <= minn)
      r = now;
    else
      l = now;
  }
  return now;
}