2795번: KAMPANJA

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

LA에 가는길과 오는길 모두 포함되어 있는 정점들을 가는길에서 방문한 순서대로 정렬한 수열을 s_1, 오는길에서 방문한 순서대로 정렬한 수열을 s_2라 하자. 또한, s_k 내에서 x는 idx_k(x)번째에 방문했다고 하자.

임의의 s, e에 대해 idx_1(s) <= idx_1(e) & idx_2(s) <= idx_2(e)를 만족하면 s<=s'<=e'<=e인 임의의 s', e'에 대해 idx_1(s')<=idx_1(e') & idx_2(s') <= idx_2(e')을 만족한다.
그렇지 않으면 가는길과 오는길의 s에서 e로 가는 최단경로가 다르므로 모순이다.

이 성질을 만족하는 경로 모양은 꽤나 단순해진다. 오는길과 가는길을 잘 정리해서 그려보면 DNA 같은 모양을 하고 있다.

이 그래프상에서 최단 거리를 구하기 위해 다음과 같은 배열 b를 정의한다.
b[i][j]: 1 ->...-> i ->...-> 2 ->...-> j ->...-> 1가 되기 위해 고용해야 하는 경호원 수
그러면 b[i][j] = min(b[i][k]+dist(j,k) - (i==j), b[k][j]+dist(i,k) - (i==j), b[j][i] + dist(j,i) - 1) (단, dist(i,i) = inf)를 만족한다.

모든 dist(i,j)쌍을 알고있다면 b[i][j]는 최단경로 알고리즘으로 구할 수 있다. 아래 소스에서는 dist(i,j)를 플로이드 알고리즘으로, b[i][j]는 벨만포드 알고리즘으로 구했다.

시간복잡도는 $O(n^2m)$

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, a[101][101], b[101][101], x[200], y[200];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) a[i][j] = b[i][j] = 1e9;
    for (int i = 0; i < m; i++) scanf("%d%d", x + i, y + i), a[x[i]][y[i]] = 1;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++) a[j][k] = min(a[j][k], a[j][i] + a[i][k]);
    b[1][1] = 1;
    for (int i = n; i--;) {
        for (int j = 1; j <= n; j++) {
            for (int k = 0; k < m; k++) {
                b[y[k]][j] = min(b[y[k]][j], b[x[k]][j] + (j != y[k]));
                b[j][x[k]] = min(b[j][x[k]], b[j][y[k]] + (j != x[k]));
            }
            for (int k = 1; k <= n; k++) b[j][k] = min(b[j][k], b[k][j] + a[k][j] - 1);
        }
    }
    printf("%d", b[2][2]);
    return 0;
}