사료 배송 경로
시간 제한1초메모리 제한1024 MB
A에서 출발해 A로 돌아오는 최단 경로를 구합니다. 방문하는 농장의 총 사료 수요가 트럭 용량을 넘지 않아야 하며, 거리와 경로를 출력합니다.
문제
당신은 사료 가게에서 일하며 배송 경로를 더 효율적으로 만들고자 합니다. 근처 농장마다 필요한 사료의 양 목록, 도로 지도, 트럭이 실을 수 있는 사료의 총량이 주어집니다. 이 데이터를 모두 입력받아 첫 번째 배송을 마치는 데 필요한 최단 거리(마일)와 그 경로를 출력하는 프로그램을 작성하시오.
배송 경로는 항상 A에서 출발하여 A로 돌아옵니다. A는 항상 배송을 출발하는 가게입니다.
참고: 같은 거리를 갖는 최단 경로가 여러 개 있을 수 있으므로 예제 데이터와 다른 경로가 나올 수 있습니다. 그래도 풀이는 올바르고 최단 거리를 출력해야 합니다.
입력
첫째 줄에는 트럭이 실을 수 있는 사료의 양을 나타내는 수가 주어진다.
둘째 줄에는 각 농장이 원하는 사료의 양이 주어진다. 농장 이름은 항상 대문자 알파벳 한 글자이다. 각 농장의 정보는 알파벳 한 글자 바로 뒤에 0부터 9까지의 숫자 한 개가 붙어 사료의 단위 수를 나타낸다. 농장의 정보는 공백 한 칸으로 구분한다.
나머지 줄에는 가게와 농장, 또는 농장끼리의 연결 관계가 주어지며, 줄 수는 정해져 있지 않다. 각 연결은 다음 형식으로 주어진다.
locationA/locationB-distanceApart
출력
최단 거리와 그 경로를 다음 형식으로 출력한다. 괄호 뒤와 하이픈의 양쪽에는 공백을 한 칸씩 둔다.
(distance) - path