atcoder ABC317 C - Remembering the Daysの勉強

DFS,BFS atcoder

atcoder.jp

・参考
Editorial - GAMEFREAK Programming Contest 2023 (AtCoder Beginner Contest 317)

・説明
　引数に頂点vとvまでの長さlengthを持つ、DFSをしていく。最大の長さをansとして、length>ansのときansを更新していく。注意点として帰りがけに頂点vを未探索にすることを忘れずに。

n,m=map(int, input().split())
g=[[]for _ in range(n)]
C=[[0 for _ in range(n)]for _ in range(n)]

for _ in range(m):
  a,b,c=map(int, input().split())
  a-=1
  b-=1
  g[a].append(b)
  g[b].append(a)
  C[a][b]=c
  C[b][a]=c
#print(C)

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


#頂点がvでlengthがvまでの長さ。
def dfs(v,length):
  global ans  #最大の長さ。
  seen[v]=1

  #ansを更新する。
  if length>ans:
    ans=length
  #print(v,ans)
  
  for nv in g[v]:
    if seen[nv]:
      continue
    dfs(nv,length+C[v][nv])
  seen[v]=0    #帰りがけに未探索にする。他の分岐で探索する為に。
  #return ans  #returnは要らない。n点について最大の長さを求めるので。
  
ans=0
for i in range(n):
  #seen=[0 for _ in range(n)]
  dfs(i,0)

print(ans)