【ABC160 D】「Line++」を解く【Python3】

abc160d

コンテスト一覧へ

 

特定の条件があるN個の頂点と、N個の辺を持つ無向グラフGに対し、頂点(i, j)の最短距離がk(=1,2,…,N-1)であるようなものの数を求める問題です。

提出
n, x, y = map(int, input().split())
li = [0] * (n - 1)
num = 0

for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        num = min(j-i, abs(i-x)+abs(j-y)+1)
        li[num - 1] += 1

for i in li:
    print(i)

Nの上限が「2×103」であるので、すべての組(i, j)を調べても間に合います。

すべての要素が0のリストを最初に作っておきます。

組(i, j)の最短距離を調べ、作成しておいたリストに加えていきます。

純粋に「j – i」をした場合と、頂点X,Yの間にある辺を通った場合とを求め、小さい方が最短距離になります。

(abs()は絶対値を出すことができます)

リストの中に答えが順番に入っているので、最後にこれを1行ずつ出力します。

スポンサーリンク

【ABC160】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。