시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 1242 | 253 | 170 | 21.767% |
고대의 보물이 묻힌 동굴이 발견되었다.
보물의 가치는 어마어마해서 한 번 탐사하는 데 성공하면 세계 최고의 부자가 될 수 있을 만했다.
한 운 좋은 고고학 회사가 탐사의 전반적인 작업을 모두 맡게 되었다.
당신은 그 회사의 인턴으로 참여중이다.
지금까지의 작업 진척도는 다음과 같다.
당신은 프로젝트 매니저 가영이가 프로젝트 초창기에 고용한 기술자이다. 당신은 이제 나희가 수치화한 이익 수치에 따라 어느 동굴들을 탐사하는 것이 최대의 이익이 될 지 계산해야 한다. 동굴을 넓히거나 동굴을 탐사하는 데 드는 추가적인 비용은 이미 다미와 라라에 의해 계산되어 있다. 이를 모두 고려하여 각 동굴마다 얻을 수 있는 최대의 이익이 각 동굴마다 수치화되어 주어질 것이다. 동굴의 지도는 아영이를 리더로 한 탐사대원들에 의해 이미 완성되어 있기 때문에 정확도는 100%에 달한다.
이제 순차적으로 탐사할 수 있는 순서대로 한 동굴에서 얻을 수 있는 손실과 이득을 계산하여 종합한 이익 표가 당신에게 주어진다. 처음으로 탐사해야만 하는, 입구의 역할을 하는 동굴은 항상 첫 번째 동굴이며, 다른 동굴들은 주어진 순서대로만 탐사할 수 있다. 어떤 동굴에서 탐사를 끝낸 뒤 이전 동굴로 장비를 다시 돌려놓는 데 필요한 추가적인 장비는 마리의 결정에 의해 도입하지 않기로 하였기에, 한 번 동굴에 입장하면 이제 그 동굴보다 깊이 있으며 서로 직접 연결된 동굴들로만 탐사를 진행할 수 있다.
모든 동굴은 첫 번째 동굴에서 도달 가능하다.
입력의 첫 줄엔 테스트 케이스의 수 T가 주어진다. (1 ≤ T ≤ 10)
각 테스트 케이스의 첫 줄엔 탐사할 수 있는 동굴의 수 N과 서로 직접 연결된 동굴 쌍의 수 E가 주어진다. (1 ≤ N ≤ 2 · 10 4; 0 ≤ E ≤ 105)
그리고 바로 다음 줄에 N개의 정수 v 1, v2, ... , vN이 주어진다. 이는 각 동굴을 탐사해서 얻을 수 있는 보물의 가치를 수치화한 것이다. (0 ≤ vi ≤ 104)
이후 E줄에 걸쳐 세 정수 a e be ce가 주어진다. 이는 동굴 ae가 be와 직접 연결되어 있으며, 동굴을 넓히고 작업 장비를 be에 들여놓는 데에 ce만큼의 작업 비용이 든다는 것을 의미한다. (1 ≤ ae, be ≤ N; 0 ≤ ce ≤ 104)
항상 탐사의 시작은 1번 동굴이다. 1번 동굴을 탐사하지 않고서는 다른 동굴에 입장하는 것이 불가능하다.
동굴 be가 ae보다 깊이 있는 경우로만 입력이 주어진다.
각 테스트 케이스마다 두 줄을 출력한다.
첫 줄엔 동굴을 탐사함으로써 얻을 수 있는 최대 이익과 그 때 방문한 동굴의 수를 출력하고,
두 번째 줄엔 그 이익을 얻을 수 있는 경로를 방문 순으로 출력한다.
이때, 그 이익을 얻을 수 있는 경로가 여러 개라면 아무 것이나 출력하면 된다.
3 1 0 10 4 3 10 20 30 40 1 2 19 1 3 23 1 4 34 4 4 10 20 30 40 1 2 10 2 4 20 1 3 20 3 4 10
10 1 1 17 2 1 3 50 3 1 3 4
ICPC > Regionals > Europe > Northwestern European Regional Contest > German Collegiate Programming Contest > GCPC 2014 D번