コンテンツにスキップ

ABC481 D - Autopilot

サイト
AtCoder
コンテスト
ABC481
問題
D - Autopilot
難易度
581

NN 頂点 MM 辺の有向グラフがあります。いまいる頂点から、次のどちらかの方法で移動できます。

  • 出ている辺の行き先のうち、番号が最小の頂点に燃料 00 で移動する。
  • 出ている辺の行き先を好きに選び、燃料 11 で移動する。

頂点 SS から頂点 TT へ移動するのに必要な燃料の最小値を求める問題です。到達できなければ −1-1 を出力します(2≤N≤2×1052 \le N \le 2 \times 10^5、1≤M≤2×1051 \le M \le 2 \times 10^5)。

各頂点 uu から出ている辺の行き先のうち、番号が最小の頂点へはコスト 00、それ以外の頂点へはコスト 11 の辺を張った新しいグラフを作ります。このグラフで SS から TT への最短距離が答えです。

辺のコストは 00 か 11 で非負なので、ダイクストラ法で求められます。計算量は、行き先のソートも含めて O((N+M)log⁡(N+M))O((N + M) \log (N + M)) です。コストが 00 と 11 だけなので 01-BFS でも求められ、その場合は最短路の部分が O(N+M)O(N + M) になります。

ダイクストラ法については ダイクストラ法のリンク集 も見てください。

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) は、頂点番号から 11 を引き、重みなしの有向辺として MM 本の辺を読みます。

g で頂点 u から出ている辺の行き先を tmp に集めてソートし、先頭(番号が最小の頂点)へはコスト i > 0 すなわち 00、それ以外へは 11 の辺を h に張ります。

shortest_path(h, S) は、h での S から各頂点への最短距離をダイクストラ法で求めます。到達できない頂点の距離はとても大きな値になります。到達できるときの答えは、同じ辺を 2 回使わない経路で考えれば MM 以下なので、MM より大きければ −1-1 を出力しています。

使用ライブラリ:cpp_include@4b58304