문제 설명

개미집은 N개의 방, 1~N번 까지 번호가 부여되어 있음.

굴을 타고 한 방에서 다른 방으로 갈 수 있는 경로는 항상 존재하며 유일하다.

-> 다음과 같이 1을 루트노드로 하는 트리 모양으로 그려진다.

간선의 가중치가 존재, 특정 노드에서 시작해서 1에 가장 가깝게 도달할 수 있는 노드를 출력하라.

1번 풀이 (dfs, 누적합 혼합)

한번 해봤는데 됐던 풀이이다.
항상 특정 노드에서 1에 가깝게 움직이는 경우는 한가지만 존재한다. 라는 점에서 착안했다.

트리라고 가정했을때 1번 노드(root node)에서 모든 리프노드들 까지 가는 경우의 수는 유일하다.
그러므로 root node에서 다른 모든 노드까지의 거리를 계산한다.

void mindist(){
    queue<int>q;
    q.push(1);
    while(!q.empty()){
        int cur = q.front(); q.pop();
        for(auto node : v[cur]){
            if(dist[node.first] > dist[cur] + node.second){
                dist[node.first] = dist[cur] + node.second;
                q.push(node.first);
            }
        }
    }
}

다시 생각해보면 특정 노드에서 1까지 올라가는 경로는 항상 유일하다.
그러므로 모든 노드에서 1까지 가는 경로를 이전에 계산해놓은 누적합을 통해 얼마나 갈 수 있는지 체크하면 된다.

for(int i=1; i<=n; i++){
        int curnode = i;
        int distsum = ant[i];
        while(1){
            if(curnode == 1){
                cout<<curnode<<'\n';
                break;
            }
            int checknode;
            for(auto node : v[curnode]){
                if(dist[node.first] > dist[curnode])
                    continue;
                checknode = node.first;
                distsum -= dist[curnode] - dist[node.first];
                break;
            }
            if(distsum < 0)
                break;
            curnode = checknode;
        }
        if(curnode != 1)
            cout<<curnode<<'\n';
    }

2번 풀이 (sparse table)

특정 노드에서 1까지 올라가는 경로를 다시 생각해보면 올라가는 간선이 하나인 유향 그래프로 생각할 수 있다. 그러므로 특정 노드에 대한 sparse table을 생각할 수 있다.

중요한 것은 노드간의 가중치가 존재하기 때문에, sparse table을 만들어 줄 때 부모 노드, 간선의 가중치의 합을 생각해 주어야 한다는 것 이다.

pair<ll,ll> table[18][100001];

일단 모든 노드에 대해 각 노드의 첫번째 부모 노드의 번호와 간선의 가중치를 초기화 해준다. (bfs, table[0][노드번호] 가 2^0, 즉 1번째 부모 노드를 가리킨다.)

void bfs(){
    queue<int>q;
    bool check[100001] = {0};
    q.push(1);
    check[1] = 1;
    while(!q.empty()){
        int cur = q.front(); q.pop();
        for(auto e : v[cur]){
            if(check[e.first]) continue;
            table[0][e.first] = make_pair(cur, e.second);
            check[e.first] = 1;
            q.push(e.first);
        }
    }
}

그 후 2^i번째 부모 노드에 대한 정보를 초기화한다.

 for(int i=1; i<=17; i++)
        for(int j=1; j<=N; j++){
            table[i][j].first = table[i-1][table[i-1][j].first].first;
            table[i][j].second = table[i-1][table[i-1][j].first].second + table[i-1][j].second;
        }

그리고 log2 N부터 움직일 수 있는 만큼 노드를 움직인다. 그때 target_node를 체크하여 움직일 수 있는 경우 target_node를 그 노드로 바꾸어 계산이 원할하게 되도록 한다.

for(int i=1; i<=N; i++){
        int target_node = i;
        for(int j=17; j>=0; j--){
            if(table[j][target_node].first != 0 && table[j][target_node].second <= ant[i]){
                ant[i] -= table[j][target_node].second;
                target_node = table[j][target_node].first;
            }
        }
        cout<<target_node<<'\n';
    }