読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

square869120Contest #1 C - お金の街 (The Money Town)

問題

C: お金の街 (The Money Town) - square869120Contest #1 | AtCoder

街i(i = 1..n)にDi円落ちている。同じ街を2度通らないように進むとき、拾えるお金の最大値はいくらか、という問題。

解法

DFS。お金の最大値は逆順に求まる(コード参照)。

def dfs(i):
    if done[i]:
        return 0
    
    done[i] = True
    
    mx = 0
    
    for j in graph[i]:
        mx = max(mx, dfs(j))
    
    done[i] = False
    
    return D[i] + mx
 
 
N, K = map(int, input().split())
D = []
for i in range(N):
    D.append(int(input()))
graph = [set([]) for i in range(N)]
for i in range(K):
    x, y = map(int, input().split())
    x -= 1; y -= 1;
    graph[x].add(y)
    graph[y].add(x)
 
mx = 0
for i in range(N):
    done = [False for i in range(N)]
    mx = max(mx, dfs(i))
 
print(mx)