(C++) 백준 1005 ACM Craft

문제 및 풀이

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

다익스트라 문제로 게임 개발과 풀이가 유사하다
(https://velog.io/@minayeah/C-백준-1516-게임-개발)

다만 이 문제는 특정 건물(w)에 대해 최소 시간을 구하는 문제라 처음에는 이걸 따져가면서 구해야 되나? 생각했는데 (w를 짓기 위해 지어져야 되는 건물인지 아닌지)
굳이 그럴필요 없이 건물 w에 연결된 edge값이 0이 될 때까지만 queue를 돌려서 답을 찾으면 된다.

처음에 코드를 잘못짜서 edge가 0이 될 때에만 건물 짓는 시간을 갱신했는데 node가 나올때 마다 계속해서 갱신해야 최소 시간을 찾을 수 있다

        for(int i=0; i<v[tmp].size(); i++){
            int next = v[tmp][i];
            if(--D[next]==0) {
                q.push(next);
            }
            minT[next] = max(minT[next], minT[tmp]+Time[next]); // <- 이부분
        }
    }

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 1000000000;
const int MAX = 1000;
int T, N, K, X, Y, W;
int Time[1005];
int D[1005];
int minT[1005];
vector<int> v[1005];


int solve(int x){

    queue<int> q;

    for(int i=1; i<=N; i++) {
        if(D[i]==0) {
            minT[i]=Time[i];
            q.push(i);
        }
    }


    while(!q.empty()){

        int tmp = q.front(); q.pop();
        if(tmp==x) return minT[x];

        for(int i=0; i<v[tmp].size(); i++){
            int next = v[tmp][i];
            if(--D[next]==0) {
                q.push(next);
            }
            minT[next] = max(minT[next], minT[tmp]+Time[next]);
        }
    }

}





int main(){
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>T;

    while(T--){

        cin>>N>>K;

        for(int i=1; i<=N; i++) {
            v[i].clear();
            D[i]=0;
            minT[i]=-1;
        }

        for(int i=1; i<=N; i++) cin>>Time[i];
        for(int i=0; i<K; i++){
            cin>>X>>Y;
            D[Y]++;
            v[X].push_back(Y);
        }

        cin>>W;
        cout<<solve(W)<<'\n';

    }
}