問題はこちら
個の点がある。その点に対して、以下のように回の操作を行い、辺を追加する。
- となる頂点と頂点 の間にコストの辺を追加する。
最終的な頂点からまでの最短距離を求めよ。
以降は0-indexとして話を進める。
解法1 - seg木でdp
が与えられた時に、 までの最小コストは、「」と「に到達する最小コスト + 」の小さい方 である。
なので、与えられた辺のクエリを、 で昇順にして辺を張りながら上記を実装すれば正しい答えは得られそう。
しかし愚直に計算すると、一つのクエリに対して全ての頂点の組み合わせの最小コストを見なければならないので、 となり間に合わない。
ここでのボトルネックは、「に到達する最小コスト」を計算するところで、ここを毎回線形探索すると間に合わない。そこで、seg木を使うことで高速に区間の最小値を求め、それを用いて までの最小コストを更新すれば、 となり間に合う。(なお、区間クエリ、点更新なので遅延セグ木である必要はない。)
dp[i] := 頂点iに到達するための最小コスト
segtree := 区間ごとの最小コストを管理する
dp[R_i] = min(dp[R_i], segtree.query(L_i, R_i) + c
(頂点rに到達できる最小コストは、区間[l, r]に到達する最小コスト + c)segtree[R_i] = dp[R_i]
(新しい最小値でseg木自体を更新)
解答
Submission #8393394 - NIKKEI Programming Contest 2019-2
以下はその抜粋部分。
struct edge { ll from, to, cost; edge(ll from, ll to, ll cost) : from(from), to(to), cost(cost) {}; }; typedef vector<edge> ve; void solve() { ll n, m; cin >> n >> m; auto fm = [](ll a, ll b) { return min(a, b); }; SegmentTree<ll, ll> tree(n + 1, fm, ll_inf); ve es; rep(i, m) { ll l, r, c; cin >> l >> r >> c; l--, r--; es.eb(edge(l, r, c)); } sort(all(es), [](edge &a, edge &b) { if (a.from == b.from) return a.to < b.to; return a.from < b.from; }); vl dp(n, ll_inf); tree.update(0, 0); dp[0] = 0; rep(i, m) { ll l = es[i].from, r = es[i].to, c = es[i].cost; ll t = tree.query(l, r); dp[r] = min(dp[r], t + c); tree.update(r, dp[r]); } ll ans = dp[n - 1]; if (ans == ll_inf) { cout << -1 << '\n'; return; } cout << ans << '\n'; }
解法2 - 工夫してダイクストラ
これがeditorialの解法。 今回の問題における辺の張り方の本質は、 から まで、 全ての となるような頂点の組 の距離が等しい という点。なので、 から に辺を張り、その間の点は全てどちらかと同じ点のように扱えると楽である。(ここまでは考えたけどどうやって実現するのかわからなかった。)
そこで、まず全ての頂点 にコスト0の有向辺を張ってあるグラフを考える。このグラフに対して から に有向辺を張ると、コスト で、その間にある全ての頂点に移動可能になる。コスト0の辺を貼ることによって最短距離が変わることはないので、答えはこのグラフに対してダイクストラを行えば求まる。
計算量は で間に合う。
解答
Submission #8392845 - NIKKEI Programming Contest 2019-2
以下はその抜粋部分。
void solve() { ll n, m; cin >> n >> m; Graph g(n); rep(i, n - 1) g.add(i + 1, i, 0); rep(i, m) { ll l, r, c; cin >> l >> r >> c; g.add(--l, --r, c); } ll ans = g.dijkstra(0).back(); cout << (ans == ll_inf ? -1 : ans) << '\n'; }
関連
- seg木でdpする他の問題 : Codeforces Round #587 (Div. 3) F. Wi-Fi - ARMERIA
- 似たような問題: C - 蛍光灯