ABC481 D - Autopilot
- サイト
- AtCoder
- コンテスト
- ABC481
- 問題
- D - Autopilot
- 難易度
- 581
頂点 辺の有向グラフがあります。いまいる頂点から、次のどちらかの方法で移動できます。
- 出ている辺の行き先のうち、番号が最小の頂点に燃料 で移動する。
- 出ている辺の行き先を好きに選び、燃料 で移動する。
頂点 から頂点 へ移動するのに必要な燃料の最小値を求める問題です。到達できなければ を出力します(、)。
各頂点 から出ている辺の行き先のうち、番号が最小の頂点へはコスト 、それ以外の頂点へはコスト の辺を張った新しいグラフを作ります。このグラフで から への最短距離が答えです。
辺のコストは か で非負なので、ダイクストラ法で求められます。計算量は、行き先のソートも含めて です。コストが と だけなので 01-BFS でも求められ、その場合は最短路の部分が になります。
ダイクストラ法については ダイクストラ法のリンク集 も見てください。
C++
#include "shogo-library/base/all"#include "shogo-library/graph/shortest-path.hpp"#include "shogo-library/utility/container_func.hpp"
void solve() { LL(N, M, S, T); S--, T--; Graph<> g(N), h(N); g.read(M, -1, false, true); rep(u, N) { vl tmp; for (ll v : g[u]) tmp.push_back(v); sort(tmp); rep(i, len(tmp)) { h.add_directed_edge(u, tmp[i], i > 0); } } ll ans = shortest_path(h, S).dist[T]; print(ans > M ? -1 : ans);}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}g.read(M, -1, false, true) は、頂点番号から を引き、重みなしの有向辺として 本の辺を読みます。
g で頂点 u から出ている辺の行き先を tmp に集めてソートし、先頭(番号が最小の頂点)へはコスト i > 0 すなわち 、それ以外へは の辺を h に張ります。
shortest_path(h, S) は、h での S から各頂点への最短距離をダイクストラ法で求めます。到達できない頂点の距離はとても大きな値になります。到達できるときの答えは、同じ辺を 2 回使わない経路で考えれば 以下なので、 より大きければ を出力しています。
使用ライブラリ:cpp_include@4b58304