[AtCoder] ABC 087 D – People on a Line

問題

方針

座標間の距離が与えられるので、相対的な位置が分かります。したがって、ある座標の値を \( x_i = 0 \) として、\( M \) 個の情報に誤りがあるかどうかを調べます。

グラフ

各座標をグラフの頂点として、\( M \) 個の辺からなるグラフを考えます。\( M \) 個の情報から隣接リストを作成します。この隣接リストに座標間の距離の情報も追加しておきます。この座標間の距離は辺の重みではないことに注意します。例えば、\( (L_i, R_i, D_i) \) という情報から、頂点 \( L_i \) の隣接する頂点は \( R_i \) であり、距離は \( D_i \) であり、頂点 \( R_i \) の隣接する頂点は \( L_i \) であり、距離は \( -D_i \) であるという隣接リストが得られます。

幅優先探索

よくあるグラフの幅優先探索を行います。一度も訪れたことがない頂点 \( i \) の座標を \( x_i = 0 \) として、座標 \( i \) を含むグラフを走査します。このグラフを走査するなかで、座標の値を更新してき、誤りがあるかどうかを調べます。例えば、グラフ \( G \) の頂点が \( (1, 2, 3) \) であり、点 \( 1 \) に隣接する頂点が \( 2, 3)\) であり、頂点 \( 2 \) に隣接する頂点が \( 3 \) であるとします。ここで、 頂点 \( 1 \) から幅優先探索を行うと、\( x_2, x_3 \) の値が定まります。次に、頂点 \( 2 \) から頂点 \( 3 \) へ訪れたとき、\( x_3 \) の値が更新されるとき誤りがあることになります。

コード