Eau de Cologne
Yukicoder No. 14 최소공배수 정렬 문제 링크 문제 최소공배수를 막 배운 Larry는, 최소공배수 정렬을 하기로 했습니다. 여기서, "최소공배수 정렬"은, $N$개의 정수가 주어지고(중복을 포함할 수 있습니다), 각각을 $a_i \ ( 1 \le i \le N)$이라고 합시다. $a_1$을 고정하고, $a_2 \sim a_N$에 대해 각각 $a_1$과의 최소공배수를 구해서, 그 최소공배수가 작은 순으로 수열을 정렬합니다. (최소공배수가 같은 것이 여럿 있으면, 원래 수가 작은 것을 우선으로 합니다) Larry는, 이런 방식으로 정렬한 수열에 새로 $a_1 \cdots a_N$이란 이름을 붙이고, 조작을 계속합니다. 다음에는 $a_2$를 고정해서 ($a_1$도 고정한다), $a_3 \sim a_..
Yukicoder No. 1 길 바로 가기 문제 링크 문제 $N$개의 마을이 있습니다. 각각에는 $1$부터 $N$까지의 번호가 붙어있습니다. 각각의 도시는 직접 길로 연결되어 있을 수도, 아닐 수도 있습니다. 각 길은 마을 $S_i$부터 마을 $T_i$까지 가는 데에 비용 $Y_i$엔이 들고, $M_i$ 단위시간이 듭니다. 당신은 마을 $1$에 있습니다. $N$번 마을에 가고 싶습니다. 도로를 몇 개 사용하든 상관없지만, 당신은 $C$엔을 가지고 있습니다. (즉, 사용한 비용 $Y_i$의 합이 $C$를 넘어서는 안 됩니다.) 그중 가장 빠른 경로를 사용할 때, 드는 총 시간을 출력해 주세요. 이 제약 안에서 도착할 수 있는 방법이 없는 경우 $-1$을 출력해주세요. 입력 $1$번째 줄에는, 마을의 수를 ..