#include #include #include #include using namespace std; int main(void) { // 입력 int t; // 테스트 케이스 수 cin >> t; vector output; for (int tc = 0; tc < t; tc++) { // 입력 int n, k; cin >> n >> k; int craftTime[1001]; for (int j = 0; j < n; j++) cin >> craftTime[j + 1]; vector> need0(1001); // key: target, value: needs vector> next0(1001); // key: this craft, value: next craft for (int j = 0; j < k; j++) { int x, y; cin >> x >> y; need0[y].push_back(x); // y를 만들기 위해 필요한 것들 x next0[x].push_back(y); // x를 만들고 나서 만들 수 있는 것들 y } int w; cin >> w; // 처리 vector answer(n + 1, 0); vector visited(n + 1, false); // 방문 여부 체크 queue bfs; bfs.push(w); visited[w] = true; // 필요한 건설 항목들 모두 bfs로 탐색 while (!bfs.empty()) { int i = bfs.front(); bfs.pop(); // 현재 건설 항목을 만들기 위해 필요한 건설 항목들 탐색 for (int need : need0[i]) { if (!visited[need]) { visited[need] = true; bfs.push(need); } } } // 각 건설 항목의 시간을 계산 // 뒤에서부터 진행하면서 건설 시간을 계산 while (!bfs.empty()) { int i = bfs.front(); bfs.pop(); // 이 건설 항목을 만들고 나서, 그걸로 만들 수 있는 다른 건설 항목들 시간 갱신 for (int nextCraft : next0[i]) { answer[nextCraft] = max(answer[nextCraft], answer[i] + craftTime[i]); } } output.push_back(answer[w] + craftTime[w]); } // 출력 for (int i : output) cout << i << '\n'; }

제출 #36392

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: