백준 4013 ATM C++
https://www.acmicpc.net/problem/4013 주어진 그래프에서 목표 지점 중 하나까지 도달하는 경로 중 최대 cost를 얻을 수 있는 값을 구하는 문제입니다. 먼저 각 경로를 SCC로 묶으면, SCC 내에서는 해당 노드 cost 합을 얻을 수 있습니다. 그리고 SCC 간의 그래프에 대해 경로 찾기 알고리즘 등으로 최대 cost를 계산하면 됩니다. 그리고 계산된 각 scc까지의 최대 cost에 대해, 커리 가게 존재 유무를 체크하여, 최종 결과를 구하면 됩니다. 저는 edge 개수와 node 개수 최대값이 동일해, SPFA를 적용했습니다.(다익스트라도 해보니 통과하긴하지만, 아무래도 sparse한 그래프라 더 느림) 코드는 아래와 같습니다. #include #include #incl..
알고리즘/백준
2025. 3. 16. 21:55