[Baekjoon - 22443] Minus One

난이도: Gold II

 

태그

• Breadth-First Search
• Combinatorics
• Meat In the Middle (알고 있을 필요는 없지만, 뭔가 그런 느낌이 있다.)

 

풀이

1. 원래의 최단 경로를 알고 있을 때, 간선을 하나 추가한 뒤의 최단 경로는?

원래의 최단 경로를 $[s=v_0,v_1,\dots ,v_k=t]$라고 하고, 추가된 간선을 $x,y$라고 합시다.

그럼, 새로운 그래프의 최단 경로는 원래의 최단경로이거나, $[s,\dots ,x,y,\dots ,t]$라는 새로운 경로가 됩니다.

 

$d(v,w)$를 $v$에서 $w$로 가는 최단 경로의 길이라고 하면,

우리가 찾은 경로의 길이는 $d(s,x)+1+d(y,t)$가 됩니다.

 

2. 간선을 추가한 뒤의 최단 경로가 이전의 최단 경로 - 1이 되려면?

$d(s,x)+1+d(y,t)=k-1$이므로, $d(s,x)+d(y,t)=k-2$여야 합니다.

 

3. $d(s,x)$를 고정할 때, 가능한 경우는?

$d(s,x)$가 고정되면, $d(y,t)$ 역시 고정됩니다.

이 때의 경우의 수는 $x$를 고르는 경우의 수 × $y$를 고르는 경우의 수가 되고,

$x$를 고르는 경우의 수는 $d(s,x)$를 만족하는 $x$의 개수가 됩니다.

$y$ 역시 비슷하게, $d(y,t)$를 만족하는 $y$의 개수가 되겠죠.

 

4. 코드

vector<int> adj[100020];
 
int dis[2][100020];
int num[2][100020];
void bfs(int idx, int st){
    memset(dis[idx], -1, sizeof(dis[idx])); dis[idx][st] = 0; num[idx][0] += 1;
    queue<int> q; q.push(st);
    while (!q.empty()){
        int now = q.front(); q.pop();
        for (int nxt : adj[now]){
            if (dis[idx][nxt] != -1){ continue; }
            dis[idx][nxt] = dis[idx][now]+1; num[idx][ dis[idx][nxt] ] += 1;
            q.push(nxt);
        }
    }
}
 
void Main(){
    int n, m, st, ed; cin >> n >> m >> st >> ed;
    while (m--){
        int v, w; cin >> v >> w;
        adj[v].push_back(w); adj[w].push_back(v);
    }
    bfs(0, st); bfs(1, ed);
    int d = dis[0][ed];
    ll ans = 0;
    //for (int i = 0; i <= n; i++){ cout << "NUM " << i << "   " << num[0][i] << ' ' << num[1][i] << endl; }
    for (int i = 0; i <= d-2; i++){
        ans += 1LL*num[0][i]*num[1][d-2 - i];
    }
    cout << ans;
}