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;
}

11657번: 타임머신

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


$O(nm)$

벨만포드 알고리즘을 사용한다.

#include<cstdio>
int n, m, a[6000], b[6000], c[6000], t[501], last;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) scanf("%d%d%d", a + i, b + i, c + i);
    for (int i = 2; i <= n; i++) t[i] = 1e9;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) if (t[a[j]]<1e9&&t[b[j]]>t[a[j]] + c[j]) {
            t[b[j]] = t[a[j]] + c[j];
            last = i;
        }
    }
    if (last == n - 1) puts("-1");
    else for (int i = 2; i <= n; i++) printf("%d\n", t[i] < 1e9 ? t[i] : -1);
    return 0;
}