백준 15971 두 로봇

문제 URL : https://www.acmicpc.net/problem/15971

 

문제접근법 :  

트리 문제입니다. 

시작지점에서 도착지점까지갔을때 해당간선 하나만 제거했을때 그비용이 최소가 되는점을 찾으면됩니다.

bfs 당연히되지만

트리라서 유일경로만 나오기때문에 dfs도 가능합니다.

스타트 지점에서 도착지점까지 왔을때 해당 경로를 다시 역으로 추적해서 그간선들중 가장 비싼 간선 한개만 제거해주면됩니다.

 

소스코드 : 

import sys
from collections import deque
sys.setrecursionlimit(2000000)
input =sys.stdin.readline
n,s,e = map(int,input().split())
adj =[[] for i in range(n+1)]
cost =[0]*(n+1)
parent = [-1]*(n+1)
for i in range(n-1):
    a,b,c = map(int,input().split())
    adj[a].append((b,c))
    adj[b].append((a,c))

def dfs(cur,p=0,total=0):
    cost[cur]=total
    parent[cur]=p
    for next,c in adj[cur]:
        if next==p:continue
        dfs(next,cur,total+c)

dfs(s)
p = e
_max = 0
while p!=s:
    _max = max(_max,cost[p]-cost[parent[p]])
    p=parent[p]
print(cost[e]-_max)

 

궁금한점 혹은 모르는점 논리적인 오류등

어떤 질문이든 댓글은 언제나 환영입니다.