[Baekjoon] 16562. 友達の雨[G 3]
7655 ワード
📚 質問する
https://www.acmicpc.net/problem/16562
📖 に答える
接続リストの問題.接続されたものの中で、最小の値を返します.
最小価格を加算して、手元のお金より多ければoh noを出力します.
多くのDFSをstackとして用いて解決したが,再帰関数で解いた.
再帰深さは制限され,深さ制限範囲はさらに拡大して解決される.
📒 コード#コード#
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
def dfs(cur): # DFS 재귀 함수
visited[cur] = 1
fee = arr[cur] # 요금의 최소 값
for nxt in v[cur]:
if visited[nxt]:
continue
fee = min(fee, dfs(nxt))
return fee # 최소 요금 리턴
n, m, k = map(int, input().split())
arr = [0] + list(map(int, input().split()))
v = [[] * (n + 1) for _ in range(n + 1)] # 인접리스트에 관계를 담는다.
for _ in range(m): # 그래프에 값을 넣어준다.
a, b = map(int, input().split())
v[a].append(b) # 서로 친구니까 방향없는 그래프
v[b].append(a)
visited = [0 for _ in range(n + 1)] # 방문 표시
total = 0
for i in range(1, n + 1):
if visited[i] == 0:
total += dfs(i)
if total > k:
print("Oh no")
break
else:
print(total)
🔍 結果
Reference
この問題について([Baekjoon] 16562. 友達の雨[G 3]), 我々は、より多くの情報をここで見つけました https://velog.io/@yunhlim/Baekjoon-16562.-친구비-G3テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol