Codeforces Round #372 (Div. 1) B. Complete The Graph

codeforces.com

Codeforces Round #372 Editorial - Codeforces

解法

辺のコストを1つあげると、最短経路のコストは0か1増加する。 広義単調増加なので、割り当てるコストの総和を2分探索で求めればよい。 辺のコストの割り当て方は適当でよい。

gist.github.com