BOJ 14907 - 프로젝트 스케줄링

BOJ 14907 - 프로젝트 스케줄링

흔한 유형의 위상정렬 기본문제이다.

입력만 잘 처리해주고 $d_i$를 알파벳 $i$가 끝날 수 있는 최소 시간이라고 둔다.

초기에 어떤 들어오는 간선도 없는 알파벳들은 $d_i=w_i$ 처럼 초기화 후 큐에 넣고, 그렇지 않은 알파벳들은

$d_i=Max_{j \in (j \to i)} \{d_j+w_i\}$ 처럼 계산해줄 수 있다.

void solve() {
#ifdef LOCAL
   freopen("./../in.txt", "r", stdin);
   //freopen("./../out.txt", "w", stdout);
#endif
   string raw;
   int n;
   vi cost(26, -1), in(26);
   vvi edges(26);
   while (getline(cin, raw)) {
      vs splited = split(raw);
      int to = splited[0][0] - 'A';
      cost[to] = stoi(splited[1]);

      if (sz(splited) >= 3) {
         for (char c: splited[2]) {
            edges[c - 'A'].pb(to);
            in[to]++;
         }
      }
   }
   queue<int> q;
   vi dp(26, -1);
   for (int i = 0; i < 26; i++) {
      if (cost[i] != -1 && in[i] == 0) {
         q.push(i);
         dp[i] = cost[i];
      }
   }
   while (sz(q)) {
      int cur = q.front();
      q.pop();
      for (int to: edges[cur]) {
         dp[to] = max(dp[to], dp[cur] + cost[to]);
         in[to]--;
         if (!in[to]) q.push(to);
      }
   }
   cout << maxe(dp);
}