백준8452 그래프와 쿼리

작성일 | In

문제 링크

  • http://icpc.me/8452

문제 출처

  • 2011 POI ONTAK 31번

사용 알고리즘

  • BFS
  • 오프라인 쿼리

풀이

간선을 끊는 쿼리가 있다는 점을 보면서 오프라인 방식을 고려해볼 수 있습니다.
쿼리를 거꾸로 처리해주면 간선을 끊는 쿼리가 간선을 이어주는 쿼리로 바뀌게 됩니다.

먼저, 제거해야 할 간선들을 모두 제거한 상태에서 BFS를 돌려 최단거리를 모두 구해줍시다.
간선이 추가되면 최단 거리가 줄어들 수는 있지만, 늘어나지는 않습니다.
간선이 추가돼서 최단 거리가 줄어드는 모든 경우에 대해 naive하게 BFS로 최단 거리를 갱신해주면 문제를 해결할 수 있습니다.

naive하게 갱신해주면 O(q(n+m))일 것 같지만, 거리가 감소하는 경우 혹은 도달 불가능한 정점이 도달 가능해지는 경우에만 갱신되므로 각 정점은 최대 O(M)번 방문합니다.
O(NM+Q)에 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;

int n, m, q;
int chk[101010];
vector<p> edge(1), qry;
vector<int> g[1010];
int dst[1010];
int ans[202020], pv;

void bfs(int st = 1){
    queue<int> q; q.push(st);
    while(q.size()){
        int now = q.front(); q.pop();
        for(auto i : g[now]){
            if(dst[i] > dst[now] + 1){
                dst[i] = dst[now] + 1; q.push(i);
            }
        }
    }
}

void add(int x){
    int s = edge[x].x, e = edge[x].y;
    g[s].push_back(e);
    bfs(s);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> q;
    for(int i=1; i<=m; i++){
        int s, e; cin >> s >> e; edge.emplace_back(s, e);
    }
    for(int i=0; i<q; i++){
        char c;
        int s, e; cin >> c >> e; s = c == 'U' ? 1 : 2; qry.emplace_back(s, e);
        if(s == 1) chk[e] = 1;
    }
    reverse(qry.begin(), qry.end());
    for(int i=1; i<=m; i++){
        if(!chk[i]){
            int s = edge[i].x, e = edge[i].y;
            g[s].push_back(e);
        }
    }
    memset(dst, 0x3f, sizeof dst); dst[1] = 0; bfs();

    for(auto i : qry){
        if(i.x == 1){
            add(i.y);
        }else{
            ans[pv++] = dst[i.y] > 1e8 ? -1 : dst[i.y];
        }
    }
    for(int i=pv-1; i>=0; i--) cout << ans[i] << "\n";
}