들어가며 코드트리 투어 삼성 SW 역량 테스트 2024년 상반기 오전 2번 문제입니다. 출발점이 되는 기준 도시가 존재하고, 기준 도시로부터 어떤 도시로 가는 여행 상품이 존재할 때, 여행 상품 수익 - 최단 경로 비용 가 최대가 되는 상품을 찾아 판매해 나가는 문제입니다. 각 명령에 대해 최적화를 하지 않으면 시간 초과가 나는 문제였습니다. 문제설명 코드트리 여행사는 코드트리 랜드에서 다양한 여행 상품을 만들어 관리하는 회사입니다. 코드트리 랜드는 n개의 도시와 각 도시 사이를 연결하는 m개의 간선으로 이루어져 있습니다. 각 도시는 0번부터 n - 1번까지의 번호가 붙여져 있고 각 간선은 방향성을 갖지 않습니다 . 또, 두 도시를 연결하는 간선은 여러 개가 존재 할 수 있으며, 자기 자신을 향하는