자동차경주 > 문제은행



문제은행

1659 : 자동차경주

제한시간: 1Sec    메모리제한: 128mb
해결횟수: 73회    시도횟수: 199회   



자동차 경주로는 <그림 1>의 예와 같이 표현된다. 화살표는 각 지점을 잇는 도로를 의미하며 모든 도로는 일방통행 도로로 화살표 방향으로만 움직일 수 있다.

 

07f1ee470c4ca420b78cf86b19196679_1450334 

 

자동차 경우의 코스는 1번 지점에서 출발하여 다시 1번 지점으로 되돌아오는 것이다. 단, 중간에는 1번 지점을 지나서는 안 된다. 경주로는 1번 지점을 제외한 어느 지점에서 출발하여도 1번 지점에서 다른 모든 지점으로 갈 수 있고, 다른 모든 지점에서 1번 지점으로 갈 수 있다.

 

각 도로에는 <그림 2>의 예와 같이 그 도로를 지날 때 얻는 점수가 있다.

 

07f1ee470c4ca420b78cf86b19196679_1450334 

 

1번 지점에서 출발하여 가장 많은 점수를 얻어 다시 1번 지점으로 돌아오는 팀이 우승을 하게 된다. 가장 많은 점수를 얻어 1번 지점으로 돌아오는 경로를 찾아 그 얻는 점수와 경로를 출력하는 프로그램을 작성하시오.


첫째 줄에는 지점의 개수 N이 주어진다. 각 지점에는 1부터 N까지의 서로 다은 번호가 부여된다. 둘째 줄에는 도로의 개수 M이 주어진다. 이어 M개의 줄에는 p ,q ,r의 형식으로 도로의 정보가 주어지는데 이는 p번 지점부터 q번 지점으로 갈 수 있는 도로가 있고 그 도로에 부여된 점수가 r이라는 뜻이다. 
N은 1000 이하의 자연수이고, p와 q는 1이상의 N 이하의 자연수이며 r은 100 이하의 자연수 이다.


가장 많은 점수를 얻은 경로를 찾아, 첫째 줄에는 그 얻는 점수를 출력하고 둘째 줄에는 그경로를 출력한다. 경로를 출력할 때는 지나는 지점들의 번호를 사이에 한 칸의 공백을 두어 출력한다. 
출력하는 경로는 반드시 1번 지점에서 시작하여 1번 지점으로 끝나야 한다. 만약 같은 점수를 얻는 경로가 둘 이상일 경우 그 중 하나만 출력하면 된다.

[Copy]
8
13
1 2 5
1 3 4
2 5 2
2 6 1
3 6 3
5 6 7
5 8 9
6 8 3
4 1 6
6 4 8
7 4 5
6 7 2
8 7 4
[Copy]
32
1 2 5 6 8 7 4 1






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.