問題へのリンク

問題概要

N 頂点 M 辺の重み付き無向単純グラフが与えられる。頂点 1 から頂点 N への経路のうち、「経路長が、最短路の経路長の X% 増し以下」であるようなものをすべて考えたときの、その経路に含まれる辺の重みの最大値を最小化せよ。

制約

2 <= N <= 10⁴
1 <= M <= 10⁵
0 <= T[i] <= 10⁹ (各辺の重み)

解法

二分探索法がとても自然に思い浮かぶ。

経路に含まれる辺の長さの最大値が mid 以下
経路の長さが最短路の X% 増し以下

という条件を満たすような経路が存在するかどうかを判定する問題を解けば良い。これはすなわち、

辺の重みを mid 以下のものしか使用できないという制限を課した状態での最短路が、通常の最短路の X% 増し以下であるかどうか

を判定する問題となる。Dijkstra 法を使い回す感じで解くことができる。

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int N, M, X;
typedef pair<int, long long> Edge;
vector<vector<Edge> > G;
const long long INF = 1LL<<60;
long long calc(long long limit) {
    vector<long long> dist(N, INF);
    dist[0] = 0;
    priority_queue<pair<long long,int>,
                   vector<pair<long long,int> >,
                greater<pair<long long,int> > > que;
    que.push(make_pair(0, 0));
    while (!que.empty()) {
        long long cur = que.top().first;
        int v = que.top().second;
        que.pop();
        if (cur > dist[v]) continue;
        for (auto e : G[v]) {
            if (e.second > limit) continue;
            if (chmin(dist[e.first], dist[v] + e.second)) {
                que.push(make_pair(dist[e.first], e.first));
            }
        }
    }
    return dist[N-1];
}
int main() {
    cin >> N >> M >> X;
    G.clear(); G.resize(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        long long T;
        cin >> a >> b >> T;
        --a, --b;
        G[a].push_back(Edge(b, T));
        G[b].push_back(Edge(a, T));
    }
    long long lo = 0, hi = 1LL<<33;
    long long shortest = calc(hi);
    long long limit = shortest + shortest * X / 100;
    while (hi - lo > 1) {
        long long mid = lo + (hi - lo) / 2;
        long long dist = calc(mid);
        if (dist <= limit) hi = mid;
        else lo = mid;
    }
    cout << hi << endl;
}