#include #include #include #include using namespace std; int main(void) { //입력 int t; //테스트 케이스 수 cin >> t; vector> craft; vector> need; //key: target, value: needs vector> next; //key: this craft, value: next craft vector target; for(int i = 0; i < t; i++) { int n, k; cin >> n >> k; vector craftTime(n+1, 0); for(int j = 0; j < n; j++) cin >> craftTime[j+1]; multimap order; multimap rorder; for(int j = 0; j < k; j++){ int x, y; cin >> x >> y; order.insert({y, x}); rorder.insert({x, y}); } int w; cin >> w; craft.push_back(craftTime); need.push_back(order); next.push_back(rorder); target.push_back(w); } //처리 for(int tc = 0; tc < t; tc++){ vector craftTime = craft[tc]; vector answer(craftTime.size(), 0); multimap need0 = need[tc]; multimap next0 = next[tc]; int c = craftTime.size() + 1; int w = target[tc]; int root = (need0.begin()->first); while (need0.find(root) != need0.end()) root = need0.find(root)->second; queue bfs; bfs.push(root); while(!bfs.empty()) { int i = bfs.front(); bfs.pop(); auto range = next0.equal_range(i); for(auto it = range.first; it != range.second; it++){ //필요한 건설 목록 중 가장 늦는 bfs.push(it->second); answer[it->second] = answer[it->second] < answer[i]+craftTime[i] ? answer[i]+craftTime[i] : answer[it->second]; } //craftTime[i] 정의 // int temp = 0; // auto range = need0.equal_range(i); // for(auto it = range.first; it != range.second; it++) //필요한 건설 목록 중 가장 늦는 // temp = craftTime[it->second] < temp ? temp : craftTime[it->second]; // craftTime[i] += temp; } //출력 cout << craftTime[w] + answer[w] << '\n'; } }

제출 #36189

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: