백준 1005 (C++) ACM Craft

https://www.acmicpc.net/problem/1005

1005번: ACM Craft

 

아이디어

 

위상정렬. 근데 약간의 다이나믹 프로그래밍을 곁들인...

 

위상정렬을 아는 사람이라면, 문제를 보고 위상 정렬 진행해서 

같은 노드로부터 출발하면 큰 값의 delay(d[i]) 를 더하면 되겠구나, 하고 생각했을 것이다.

 

 

 

현재 노드를 cur,
cur의 다음 노드를 nxt라고 했을때
result[nxt] 는 result[cur] + d[nxt] 중 최댓값이다.

 

 

 

 

 

틀렸습니다

를 받았다면?

 

1. memset, 배열과 queue를 초기화했는지 살펴볼것

2. MAX 값 즉 배열의 범위를 살펴볼 것

3. 위상 정렬의 순서를 살펴볼 것

 

 

 

 

 

---

 

728x90

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
using ll = long long;
const int MAX = 1001;
int t, n, k, w;
int inDegree[MAX];
vector<int> v[MAX];
int d[MAX];

void topologySort() {
    int result[MAX];
    queue<int> q;
    
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) q.push(i);
        result[i] = d[i];
    }
    for (int i = 1; i <= n; i++) {
        int cur = q.front();
        q.pop();
        for (auto nxt : v[cur]) {
            inDegree[nxt]--;
            result[nxt] = max(result[nxt], result[cur] + d[nxt]);
            if (inDegree[nxt] == 0) {
                q.push(nxt);
            }
        }
    }
    cout << result[w] << '\n';
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> t;
    while (t--) {
        cin >> n >> k;
        for (int i = 1; i <= n; i++) {
            cin >> d[i];
        }
        for (int i = 0; i < k; i++) {
            int x, y;
            cin >> x >> y;
            v[x].push_back(y);
            inDegree[y]++;
        }
        cin >> w;
        topologySort();
        memset(inDegree, 0, sizeof(inDegree));
        memset(d, 0, sizeof(d));
        memset(v, 0, sizeof(v));
    }
    return 0;
}

 

 

 

 

 

흑흑