1719 택배

가중치 무향 그래프가 주어진다. 모든 두 정점 쌍에 대하여 최단경로의 첫 번째 경유지(목적지)를 구하는 문제이다.

---

• 출력 결과가 대칭행렬이 아니다. (두 정점 사이의 최단거리가 두 정점을 잇는 간선 하나일 경우)
• A에서 B로가는 최단경로는 B에서 A로가는 최단경로와 같다.

1. 데이크스트라를 사용하는 방식

데이크스트라를 각 정점마다 실행한다. A정점에서 B정점으로의 최단거리가 갱신될 때마다 마지막으로 지나온 정점 C를 저장해놓는다. C는 B에서 A로 가는 최단경로의 첫 번째 경유지이다.

데이크스트라에서 아래 표시한 부분만 추가로 생각하면 풀리는 문제이다.
시간복잡도는 $O(VE\log_2 V)$이다. ($V$는 정점 개수, $E$는 간선 개수)

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vpii adj[200];
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    priority_queue<pii, vpii, greater<>> pq;
    int par[200][200];		#정답이 담길 배열
    for (int i = 0; i < n; ++i) {
        vi dist(n, INF);
        dist[i] = 0;
        pq.emplace(dist[i], i);
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (dist[u] < d) {
                continue;
            }
            for (auto [v, w] : adj[u]) {
                if (d + w < dist[v]) {
                    dist[v] = d + w;
                    pq.emplace(dist[v], v);
                    par[v][i] = u;	#최단거리가 갱신될 때마다 직전에 건너온 정점 갱신
                }
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j) {
                cout << "- ";
            } else {
                cout << par[i][j] + 1 << ' ';
            }
        }
        cout << '\n';
    }
    return 0;
}

2. 플로이드와샬을 사용하는 방식

초기 상태의 그래프에서 연결된 간선을 최단경로라 보고 최단경로의 첫 번째 경유지를 저장해놓는다. A정점에서 B정점으로의 최단거리가 C정점을 경유했을 때 기준으로 갱신될 때마다 A정점에서 B정점으로의 최단경로의 첫 번째 경유지를 A정점에서 C정점으로의 최단경로의 첫 번째 경유지로 갱신한다.

이것도 기존 플로이드 와샬 코드에서 아래 표시한 부분만 생각하면 되는 문제이다.
시간복잡도는 $O(V^3)$이다. ($V$는 정점 개수)

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    int adj[200][200]{};
    int par[200][200]{};		#정답이 담길 배열
    memset(adj, INF, sizeof(adj));
    memset(par, INF, sizeof(par));
    for (int i = 0; i < n; ++i) {
        adj[i][i] = 0;
    }
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        adj[u][v] = w < adj[u][v] ? w : adj[u][v];
        adj[v][u] = w < adj[v][u] ? w : adj[v][u];
        par[u][v] = v;			#초기 그래프의 상태로 답을 구해둔다.
        par[v][u] = u;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                if (adj[j][i] + adj[i][k] < adj[j][k]) {
                    adj[j][k] = adj[j][i] + adj[i][k];
                    par[j][k] = par[j][i];		#최단경로가 갱신될 때마다 처음 경유지도 갱신
                }
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j) {
                cout << "- ";
            } else {
                cout << par[i][j] + 1 << ' ';
            }
        }
        cout << '\n';
    }
    return 0;
}

시간 비교

$V$가 200, $E$가 10000인 것으로 계산하면 연산량과 소요시간은 아래와 같다.

• 데이크스트라 15,287,712 (24ms)
• 플로이드와샬 8,000,000 (12ms)