atcoder ABC 320 D - Relative Positionの説明

atcoder.jp

・説明
　DFSで解ける。Aiから行けるBiをDFSしていき、原点からの距離を(distx, disty)で管理する。
　注意点として、入力で

g[b].append((a,-1*c,-1*d))  

bから見たaの座標もappendしないといけないことに注意。

import sys
sys.setrecursionlimit(10**6)  

n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
  a,b,c,d=map(int,input().split())
  a-=1
  b-=1
  g[a].append((b,c,d))
  g[b].append((a,-1*c,-1*d))  #bから見たaの位置
#print(g)

#原点からの距離.
distx=[0 for _ in range(n)]
disty=[0 for _ in range(n)]

seen=[0 for _ in range(n)]

def dfs(v):
    seen[v]=1
    for nv,x,y in g[v]:
        if seen[nv]:
            continue
        #vから行ける点nvの距離を更新.
        distx[nv]=distx[v]+x
        disty[nv]=disty[v]+y
        dfs(nv)
        

dfs(0)

#探索済みでないなら"undecidable"を出力。
for i in range(n):
    if seen[i]==0:
        print("undecidable")
    else:
        print(distx[i],disty[i])