こんにちは。最近10時に寝て7時に起きるという小学生顔負けの生活リズムのとーです。
ABC087D
二人の人の間の距離が渡されるのでそれらの情報が矛盾していないかどうかを確認する問題
解き方としては、起点の情報から見ていって、座標の情報がまだ更新されていなかったらとりあえず今持っている情報で更新し、すでに更新されていたら、今持っている情報と更新済みの情報が矛盾しないかをチェックしていくという感じ
一つ確認し、それに連なる点の情報を見る、という作業を続けていくので、FIFOのデータ構造が使える
以下はpython3による答えのコード
from collections import deque N,M = map(int,input().split()) edge = [[] for i in range(N)] #edge[i]には点i-1に隣接する点と、距離が入る x = [float('inf')]*N #ここに点の座標の情報が入る(最初は全て未更新) for i in range(M): L,R,D = map(int,input().split()) edge[L-1].append([R-1,D]) #左から右を見るときは距離Dが入る edge[R-1].append([L-1,-D]) #右から左を見るときは距離-Dが入る for i in range(N): if x[i] == float('inf'): #座標の情報が未更新なら x[i] = 0 #ここを起点とする q = deque([i]) #起点がqに入る while len(q) > 0: #qが空になるまで続く now = q.popleft() for e in edge[now]: if x[e[0]] == float('inf'): #次に見た点が未更新なら x[e[0]] = x[now]+e[1] #今見ている点から距離+D(e[1])だけ足す q.append(e[0]) #次に見た点をqに入れる elif x[e[0]]-x[now] != e[1]: #次に見る点が更新済み且つ情報と矛盾するなら print('No') exit() print('Yes')
