BOJ 1948 - 임계경로

https://www.acmicpc.net/problem/1948 처음엔 다익스트라 변형(가중치로는 최소 힙이 아닌 최대힙을 쓰되, 진입차수 기준으로는 최소 힙)을 시도하려 했지만, 구현 하는 도중에 '우선순위 큐를 쓸 필요가 있나? 진입차수가 0인 시점에서 최장 거리임을 확정 짓는거 아닌가?'

가 떠올라서 BFS로 바끔. 다만 위상 정렬과 매우 유사하다 생각했지, 위상정렬을 의도하고 낸 문제인지는 모르고 풀었음.

풀이는 다음과 같음: 1) 한걸음 도시(one_step)에서 모든 정점까지의 최장 거리 dist를 구하고, 2) 그래프를 뒤집은 후 로마에서 모든 정점 까지의 최장 거리(= 각 정점에서 로마까지 걸리는 최장 거리) rev_dist를 구한 후 3) 그래프의 모든 각 간선(src: u, dst: v, weight: w)에 대해서, dist[u] + w + rev_dist[v] == dist[roma]를 만족한다면 해당 간선을 황금 도로로 카운트 #include