백준 2176, 합리적인 이동경로

개요

문제 링크
골드 2, Graph, DP, Dijkstra
두 점 사이를 가까워지며 이동하기

---

접근

1. 오랜만에 푸는 백준. 퇴사 후 옛 생각에 한 문제 풀어봤다. 문제는 1번 노드에서 2번 노드로 갈 때 갈수록 가까워지는 것이다.
2. 엥 그냥 플로이드-워셜이랑 비슷한거 아닌가? 근데 왜 1에서 2로 가는 경로만 묻는걸까? 싶을 수 있다. 가까워지며 이동하는 것이 헷갈리는 게념인데, 아래와 같이 생각해보자.
   1. 출발점 A에서 도착점 D로 이동할때 B와 C의 갈랫길이 있다고 생각하자.
   2. D까지 거리는 B가 5, C가 10이다.
   3. A에서 B,C까지 이동거리는 모두 1이다.
   4. 그럼 최적의 선택지는 A->B->D로 6이다. A의 최소 이동거리는 6이다. 이때는 도착점까지 최소 거리가 6->5->0으로 최소거리가 줄어드는 조건을 만족한다.
   5. 하지만 A->C->D로 간다면, C의 최소이동거리는 10이므로 6->10->0으로 이동해서 최소거리가 줄어드는 조건을 불만족한다.
3. 따라서 먼저 최소 거리를 구한 뒤, 그 최소거리가 감소하는 구간만 더해주면 된다. 최소거리는 다익스트라를 쓰고, 구간의 개수는 BFS를 생각할텐데 메모리 초과다. 그럼 DFS를 쓰냐? 하면 시간 초과다. 그래서 메모이제이션 + DFS를 쓰면 된다.
4. C언어는 min heap과 연결 list를 구현하면 되는데 왜인지 c++보다 시간이 느리다. 구현은 틀린게 없는것 같은데 이해가 안됨.

---

Pseudo code

// cost[i] : i에서 2까지 가는 최단거리
// saved[i] : i에서 2까지 가는 경로의 수
cost = dijkstra()
// x에서 2까지 가는 경로의 수
dfs(x) {
    // 저장되어 있다면 바로 return
    if (saved) return saved
    // 모든 연결점에서
    ans = 0
    for (y : graph[x]) {
        // 최단거리가 더 짧다면 (갈수록 가까워지면)
        if (cost[y] < cost[x]) {
            ans += dfs(y)
        }
    }
    return saved = ans
}
dfs(1)

---

Source code

// 2568KB, 4ms
#include <bits/stdc++.h>
using namespace std;
using str = string;
using vec = vector<int>;
using pii = pair<int, int>;
using vii = vector<pii>;
using mat = vector<vii>;
#define pb push_back

int n, m;
vec co, saved;
mat cm;

void dijkstra() {
    co = vec(n, 2e9);
    priority_queue<pii> que;
    que.push({0, 1});
    while (!que.empty()) {
        auto p = que.top();
        auto c = p.first;
        auto x = p.second;
        que.pop();
        if (co[x] < -c) continue;
        co[x] = -c;
        for (auto &y : cm[x]) {
            que.push({-(co[x] + y.second), y.first});
        }
    }
}

int dfs(int x) {
    if (saved[x]) return saved[x];
    int ret = 0;
    for (auto &y : cm[x]) {
        if (co[y.first] < co[x]) {
            ret += dfs(y.first);
        }
    }
    return saved[x] = ret;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;

    cm = mat(n);
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        cm[a].pb({b, c});
        cm[b].pb({a, c});
    }
    dijkstra();
    saved = vec(n, 0);
    saved[1] = 1;
    cout << dfs(0);
}

// 2836KB, 20ms
#include <stdio.h>
#include <stdlib.h>
#define N 1010
#define M 100010

int n, m;
int co[N], saved[N];

typedef struct {
    int c, x;
} node;

typedef struct {
    node heap[M];
    int s;
} Heap;
Heap h;

typedef struct list {
    int c, x;
    struct list* next;
} list;

list* cm[N];
void push(int a, int b, int c) {
    list* p = (list*)malloc(sizeof(list));
    p->c = c;
    p->x = b;
    if (!cm[a]) {
        cm[a] = p;
        return;
    }
    p->next = cm[a]->next;
    cm[a]->next = p;
}

void insert(Heap* h, node n) {
    int i;
    for (i = ++(h->s); (h->heap[i / 2].c < n.c) && i; i /= 2) {
        h->heap[i] = h->heap[i / 2];
    }
    h->heap[i] = n;
}
node pop(Heap* h) {
    node ret = h->heap[1];
    node last = h->heap[h->s--];
    int i, child;
    for (i = 1; i * 2 <= h->s; i = child) {
        child = i * 2;
        if (child != h->s && h->heap[child].c > h->heap[child + 1].c) child++;
        if (last.c <= h->heap[child].c) break;
        h->heap[i] = h->heap[child];
    }
    h->heap[i] = last;
    return ret;
}

void dijkstra() {
    for (int i = 0; i < n; i++) co[i] = 2e9;
    for (int i = 0; i < n; i++) h.heap[i].c = 2e9;
    node p = {0, 1};
    insert(&h, p);
    while (h.s) {
        node p = pop(&h);
        int c = p.c;
        int x = p.x;
        if (co[x] < c) continue;
        co[x] = c;
        list* q = cm[x];
        while (q) {
            node r = {co[x] + q->c, q->x};
            insert(&h, r);
            q = q->next;
        }
    }
}

int dfs(int x) {
    if (saved[x]) return saved[x];
    int ret = 0;
    list* q = cm[x];
    while (q) {
        if (co[q->x] < co[x]) {
            ret += dfs(q->x);
        }
        q = q->next;
    }
    return saved[x] = ret;
}

int main() {
    scanf("%d %d", &n, &m);
    while (m--) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        a--, b--;
        push(a, b, c);
        push(b, a, c);
    }
    dijkstra();
    saved[1] = 1;
    printf("%d", dfs(0));
}

# 40628KB, 92ms
import heapq, sys
input = sys.stdin.readline
def inp():return list(map(int, input().split()))

N, M = 1010, 100010
n, m = inp()
co, saved = [2e9] * N, [0] * N
adj = [[] for _ in range(N)]
q = []

def dijkstra():
    heapq.heappush(q, (0, 1))
    while q:
        cost, cur = heapq.heappop(q)
        if co[cur] < cost:
            continue
        co[cur] = cost
        for nxt, ncost in adj[cur]:
            heapq.heappush(q, (cost + ncost, nxt))

def dfs(cur):
    if saved[cur]:
        return saved[cur]
    res = 0
    for nxt, ncost in adj[cur]:
        if co[nxt] < co[cur]:
            res += dfs(nxt)
    saved[cur] = res
    return res

for _ in range(m):
    a, b, c = inp()
    a -= 1
    b -= 1
    adj[a].append((b, c))
    adj[b].append((a, c))

dijkstra()
saved[1] = 1
print(dfs(0))