#include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; #define foi(n) for (int i = 1; i <= n; ++i) #define foj(n) for (int j = 1; j <= n; ++j) #define fok(n) for (int k = 1; k <= n; ++k) #define fozi(n) for (int i = 0; i < n; ++i) #define fozj(n) for (int j = 0; j < n; ++j) #define fozk(n) for (int k = 0; k < n; ++k) #define PI 3.14159265358979323846 #define INF 2e9 #define ENABLE_LOG 0 #define ENABLE_TESTCASE #define MAX 1001 template void printLog(const Args &...strs) { #if ENABLE_LOG ((cout << strs), ...); cout << '\n'; #endif } // static const int dr[4] = {1, 0, -1, 0}; const int dc[4] = {0, -1, 0, 1}; int R, L, M, N, K, T; int a, b, c, u, v, w, x, y, z; // var vector adj[MAX]; queue q; int indegree[MAX]; int outdegree[MAX]; int requiredTime[MAX]; int W; void init() { foi(N) adj[i].clear(); memset(indegree, 0, sizeof(indegree)); memset(outdegree, 0, sizeof(outdegree)); cin >> N >> K; foi(N) cin >> requiredTime[i]; foi(K) { cin >> x >> y; adj[x].push_back(y); indegree[y]++; outdegree[x]++; } cin >> W; } void solution() { // Khan's algorithm if (indegree[W] == 0 && outdegree[W] == 0) { cout << requiredTime[W] << '\n'; return; } vector res[MAX]; foi(N) { if (indegree[i] == 0 && outdegree[i] != 0) q.push({i, 1}); } while (!q.empty()) { auto [curNode, curStage] = q.front(); q.pop(); res[curStage].push_back(curNode); for (int next : adj[curNode]) { if (--indegree[next] == 0) q.push({next, curStage + 1}); } } int totalTime = 0; bool isReached = false; foi(N) { if (res[i].empty() == true || isReached == true) break; int maxTime = 0; for (int idx : res[i]) { maxTime = max(maxTime, requiredTime[idx]); if (idx == W) { maxTime = requiredTime[idx]; isReached = true; break; } } totalTime += maxTime; } cout << totalTime << '\n'; } int main() { ios_base::sync_with_stdio(false); // disable synchronization C, C++ I/O cin.tie(NULL); // untie cin from cout #ifdef ENABLE_TESTCASE cin >> T; while (T--) { #endif init(); solution(); #ifdef ENABLE_TESTCASE } #endif }

제출 #89764

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: