2026-10-23
shortest.cpp
struct Edge {
int from, to, weight;
};
std::vector<std::optional<int>> shortest(int n, const std::vector<Edge>& edges) {
}
頂点に 0 から n - 1 の番号が付いたグラフがあり、edges の各要素は頂点 from から to へ一方向にだけ進める辺で、weight はその辺を通るときにかかる重みです。重みは負のこともあります。辺をたどって頂点 0 から各頂点へ行く道のうち、重みの合計が最小のものの合計を、頂点の番号順に並べて返す shortest を書いてください。頂点 0 自身は 0 で、たどり着けない頂点は std::nullopt にします。一周して元の頂点に戻る道で重みの合計が負になるものは、入力にありません。
入力例 1
shortest(4, {{2, 3, 1}, {1, 2, -3}, {0, 1, 2}, {0, 2, 5}})
出力例 1
{0, 2, -1, 0}
入力例 2
shortest(3, {{0, 1, 4}, {2, 1, -9}})
出力例 2
{0, 4, std::nullopt}
入力例 3
shortest(1, {})
出力例 3
{0}
Reference
std::vector<std::optional<int>> shortest(int n, const std::vector<Edge>& edges) {
std::vector<std::optional<int>> dist(n);
dist[0] = 0;
for (int round = 1; round < n; ++round) {
for (const auto& [from, to, weight] : edges) {
if (dist[from] && (!dist[to] || *dist[from] + weight < *dist[to])) {
dist[to] = *dist[from] + weight;
}
}
}
return dist;
}
参考実装は Bellman-Ford 法です。辺 from→to について、from までの見積もりにその辺の重みを足したほうが to の見積もりより小さければ書き換えます。この操作を辺の緩和(relaxation)といいます。最短の道は同じ頂点を2度通らないので、使う辺は多くても n - 1 本です。すべての辺を緩和する周回を1回すると、最短の道の辺が少なくとも1本ぶん先まで正しくなるので、n - 1 周で全頂点の距離が決まります。
重みが負でもよいのが、この方法を使う理由です。入力例 1 では頂点2へ直接行く辺の重みは5ですが、頂点1を経由すると 2 + (-3) = -1 で、そちらが短くなります。近い頂点から順に距離を確定させるダイクストラ法(Dijkstra's algorithm)は、確定した距離が後から短くならないことを前提にしています。負の重みの辺があるとこの前提が崩れるので、どの頂点の見積もりも最後の周まで書き換えられる Bellman-Ford 法を使います。
まだ届いていない頂点は std::nullopt のままにし、そこから出る辺は緩和しません。入力例 2 の頂点2がそうで、dist[from] が空の辺 2→1 は if の最初の条件で飛ばされます。INT_MAX のような大きな数を「届かない」の代わりにすると、そこに負の重みを足した値が本物の距離のように見えたり、正の重みを足してオーバーフローしたりします。std::optional なら、届かないことが値の範囲とは別に表せます。掲載したのは参考実装で、唯一の正解ではありません。1周の中で書き換えが1つも起きなければ、その時点でループを抜けてもかまいません。