始点ソートして、L ≦ i ≦ R でd[ i ] = min( d[ i ], d[ L ] + c ) で更新していけば終わり。 答えは d[ n-1 ] で、d[ n-1 ] = INF なら -1 を出力する d[ i ] の一点取得、L ≦ i ≦ R の区間更新なのでセグ木を使えば簡単。 import sys read = sys.stdin.buf…

まず、根になる頂点は、Bには含まれておらず、そのような点 a がただ一つ存在することが分かる。 そして、次に Ai = a となっている辺を全て取り除くと、Bに含まれない点 b が新たに1個以上現れる。その点は、a しか親になりえないので b の親は a とわかる…