これ、頂点を倍加してダイクストラする系。
問題へのリンク
問題概要
頂点 
辺の連結な無向グラフが与えられる。各辺 
には
- 通行に要する料金
円 (所持金が 以上でなければ通行できない)
- 通行に要する所要時間
秒
という属性がある。また、各頂点 では所持金を増やすことができる。
- 1 回の操作で増やせる料金は
円
- それに要する時間は
秒
となっている。同じ頂点で何度でも所持金増加操作を実施することができる。
最初、頂点 
にいて、所持金は 
円である。各頂点 
に対して、その頂点に到達するための最小の所要時間を求めよ。
制約
解法
拡張ダイクストラと言われているパターンの問題例としては、以下のものとかがある。
drken1215.hatenablog.com
所持金の大小を気にせずに普通のダイクストラ法でやろうとすると、あるところで辺 e = (u, v) の移動をするのに所持金が足りない...みたいなことになる。よって辺 e = (u, v) を通りたいなら、今までのどこかの頂点で所持金を補充しておく必要がある。でもあらかじめどの頂点で所持金を補充しておくべきかとか、よくわからない。
そこで登場するアイディアは
グラフの各頂点に、所持金の情報も持たせる。具体的には頂点 v について
- (v, 0)： 頂点 v に到達していて、所持金が 0 円であるような状態
- (v, 1)： 頂点 v に到達していて、所持金が 1 円であるような状態
- (v, 2)： 頂点 v に到達していて、所持金が 2 円であるような状態
- ...
という風にして、頂点を倍加していく
というものだ。これをすることで、
頂点 u (所持金 s 円) から、所持金 a 円 (所要時間 b 秒) を必要とする辺 e = (u, v) を通ることは、改めて頂点 (u, s) から頂点 (v, s - a) への、重み b の辺とみなせる
頂点 u (所持金 s 円) で c 円分を補充をする (所要時間 d 秒) 作業は、頂点 (u, s) から頂点 (u, s + c) への、重み d の辺とみなせる
ということになる。そして
- dp[ v ][ s ] := 頂点 v にいて、所持金 s という状態になるのに要する最小の所要時間
として、ダイクストラ法によって求めていくイメージ。なお、この問題、辺の張り方を雑にやってしまうと結構 TLE が危険になってしまう (下に簡単に注意書きした)。
このように拡張したグラフ上でダイクストラする。
さて、もう一つの気づくべきポイントとしては、今のままでは所持金上限は 
ということで計算量がヤバいことになる。しかし少し考えてみると、
- 2500 円以上あっても関係ない
- なぜなら、「一度訪れた頂点に二度以上行く意味はない」ことから、使う辺の本数は高々
本で、それぞれ最大 
円しか消費しないことから、2500 円以上あっても余る
ということに気づく。よって
if (S >= 2500) S = 2500;
という風にして良いし、拡張したグラフの各頂点も、所持金 2500 円まで考えれば良い。
計算量は、
- 頂点数：
- 辺数：
より、全体で 
になる。
#include <bits/stdc++.h>
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; }
using pll = pair<long long, long long>;
using Edge = pair<int, pll>;
using Graph = vector<vector<Edge>>;
const long long INF = 1LL<<60;
const int MAX = 2500;
int N, M;
long long S;
Graph G;
vector<long long> C, D;
void solve() {
if (S >= MAX) S = MAX;
vector<vector<long long>> dp(N, vector<long long>(MAX+1, INF));
priority_queue<pair<long long, pll>, vector<pair<long long, pll> >, greater<pair<long long, pll> > > que;
dp[0][S] = 0;
que.push(make_pair(0, pll(0, S)));
while (!que.empty()) {
auto p = que.top(); que.pop();
long long time = p.first;
int v = p.second.first;
long long s = p.second.second;
if (time > dp[v][s]) continue;
if (s + C[v] <= MAX) {
long long ns = s + C[v];
long long ntime = time + D[v];
if (chmin(dp[v][ns], ntime)) {
que.push(make_pair(ntime, pll(v, ns)));
}
}
for (auto e : G[v]) {
if (s < e.second.first) continue;
int nv = e.first;
long long ns = s - e.second.first;
long long ntime = time + e.second.second;
if (chmin(dp[nv][ns], ntime)) {
que.push(make_pair(ntime, pll(nv, ns)));
}
}
}
for (int v = 1; v < N; ++v) {
long long res = INF;
for (int s = 0; s <= MAX; ++s) chmin(res, dp[v][s]);
cout << res << endl;
}
}
int main() {
cin >> N >> M >> S;
G.assign(N, vector<Edge>());
for (int i = 0; i < M; ++i) {
long long u, v, a, b;
cin >> u >> v >> a >> b;
--u, --v;
G[u].push_back(Edge(v, pll(a, b)));
G[v].push_back(Edge(u, pll(a, b)));
}
C.resize(N); D.resize(N);
for (int i = 0; i < N; ++i) cin >> C[i] >> D[i];
solve();
}
計算量的な罠
今回の拡張ダイクストラ、実は割と罠もある。辺の貼り方を雑にやると TLE ギリギリになる。具体的には、
(u, s) から (v, s-a), (v, s-a+c), (v, s-a+2c), ... にそれぞれコストが b, b+d, b+2d, ... の辺を張る
という風にするのも自然に思えるのだ。だがこれだと、上に書いた辺の張り方に比べると、辺の本数がざっくり 2500 倍くらいになるので、TLE がかなり厳しくなる。
-
で常に 0 になるなぁ...
は、周期
で、
だけ増える
の値は不変
は単調増加
