055 임계경로

첫번째 코드

 

사실 이 문제를 풀 떄 뇌가 거의 빠져 있었다.

다음에 꼭 다시 풀어보아야 하는 문제이다.

 

코드는 책을 참고했고, 그래도 천천히 생각하면서 위상정렬 코드는 작성할 수 있을 것 같다!!

 

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
m = int(input())
A = [[] for _ in range(n+1)]
reverseA = [[] for _ in range(n+1)]
indegree = [0] * (n+1)

for i in range(m):
    s, e, v = map(int, input().split())
    A[s].append((e, v))
    reverseA[e].append((s, v))
    indegree[e] += 1

startcity, endcity = map(int, input().split())

queue = deque()
queue.append(startcity)
result = [0] * (n+1)

while queue:
    now = queue.popleft()
    for next in A[now]:
        indegree[next[0]] -= 1
        result[next[0]] = max(result[next[0]], result[now] + next[1])
        if indegree[next[0]] == 0:
            queue.append(next[0])

resultCount = 0
visited = [False] * (n+1)
queue.clear()
queue.append(endcity)
visited[endcity] = True

while queue:
    now = queue.popleft()
    for next in reverseA[now]:
        if result[next[0]] + next[1] == result[now]:
            resultCount += 1
            if not  visited[next[0]]:
                visited[next[0]] = True
                queue.append(next[0])

print(result[endcity])
print(resultCount)

 

통과!

다음에 꼭  풀어보기!!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Platinum/1948.%E2%80%85%EC%9E%84%EA%B3%84%EA%B2%BD%EB%A1%9C

programmers/백준/Platinum/1948. 임계경로 at main · ornni/programmers