부품 생산
시간 제한2초메모리 제한512 MB
부품 제작 시간과 사이클 없는 선행 조건 그래프가 주어질 때, 1번 부품을 만드는 최소 시간과 필요한 부품 수, 그리고 제작 순서를 출력한다.
문제
«Auto-2010» 기업은 전 세계적으로 알려진 자동차용 엔진을 생산한다. 엔진은 1번부터 n번까지 번호가 붙은 정확히 n개의 부품으로 이루어져 있으며, 번호 i인 부품은 pi초 동안 제작된다. «Auto-2010» 기업의 특성상, 엔진의 부품은 한 번에 하나만 제작할 수 있다. 어떤 부품을 생산하려면 미리 만들어 둔 다른 부품들이 필요하다.
«Auto-2010»의 사장은 기업에 야심 찬 과제를 내렸다. 전시회에 선보이기 위해 번호 1인 부품을 최소 시간 안에 제작하는 것이다.
부품 간의 생산 순서 의존 관계가 주어졌을 때, 번호 1인 부품을 생산할 수 있는 최소 시간을 구하는 프로그램을 작성해야 한다.
입력
입력 파일의 첫째 줄에는 엔진 부품의 개수 n (1 ≤ n ≤ 100000)이 주어진다. 둘째 줄에는 각 부품의 제작 시간을 초 단위로 나타내는 n개의 자연수 p1, p2 … pn이 주어진다. 각 부품의 제작 시간은 109초를 넘지 않는다.
이어지는 n개의 줄은 각각 부품 생산의 특성을 나타낸다. 여기서 i번째 줄에는 부품 i를 생산하는 데 필요한 부품의 개수 ki와 그 번호들이 주어진다. 모든 ki의 합은 200000을 넘지 않는다.
부품 생산에 순환 의존 관계는 존재하지 않는 것으로 알려져 있다.
출력
출력 파일의 첫째 줄에는 두 수가 주어진다. 번호 1인 부품을 가장 빠르게 생산하는 데 필요한 최소 시간(초)과 이를 위해 생산해야 하는 부품의 개수 k이다. 둘째 줄에는 번호 1인 부품을 가장 빠르게 생산하기 위해 생산해야 하는 순서대로 k개의 부품 번호를 공백으로 구분하여 출력한다.