[백준 2398] 3인 통화

문제

www.acmicpc.net/problem/2398

 

알고리즘

Dijkstra

 

풀이

세명이 통화를 하기 위해 간선들을 연결하기 위한 최소비용, 그 때 사용하는 간선들을 출력하는 문제입니다.

 

사람들이 그래프 위에서 움직여 최적의 장소에서 모이는 문제로 해석해보겠습니다. 각 사람마다 각 노드마다의 최소거리를 알 수 있다면 즉, 한 지점마다 세 사람의 최소거리를 안다면 우리는 어디 지점에서 세 사람이 만나야 하는지 알 수 있습니다. 사람마다 다익스트라를 돌려 총 세번의 다익스트라를 수행하고 그때마다 그 사람이 어디 노드에서 어디 노드로 갔는지를 기록하면 됩니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

const int MAXN = 1e4 + 5;
typedef pair<int, int> pii;

int N, M, ansDist, ansHere;
int dist[3][MAXN];
int comeFrom[3][MAXN];
int start[3];
vector<pii> adj[MAXN];

void dijkstra(int idx, int here) {
    dist[idx][here] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.emplace(0, here);

    while (!pq.empty()) {
        auto [hdist, u] = pq.top();
        pq.pop();
        if (dist[idx][u] < hdist)
            continue;
        for (auto [v, w] : adj[u]) {
            if (dist[idx][u] + w < dist[idx][v]) {
                dist[idx][v] = dist[idx][u] + w;
                comeFrom[idx][v] = u;
                pq.emplace(dist[idx][v], v);
            }
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    memset(dist, 0x3f, sizeof(dist));
    ansDist = 0x3f3f3f3f;
    cin >> N >> M;
    rep(i, M) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    rep(i, 3) {
        cin >> start[i];
        dijkstra(i, start[i]);
    }
    REP(i, N) {
        long long cand = 0;
        rep(j, 3) {
            cand += dist[j][i];
        }
        if (cand < ansDist) {
            ansHere = i;
            ansDist = cand;
        }
    }
    int cnt = 0;

    rep(i, 3) {
        int ah = ansHere;
        while (ah != start[i]) {
            ah = comeFrom[i][ah];
            ++cnt;
        }
    }
    cout << ansDist << ' ' << cnt << '\n';
    rep(i, 3) {
        int ah = ansHere;
        while (ah != start[i]) {
            cout << ah << ' ' << comeFrom[i][ah] << '\n';
            ah = comeFrom[i][ah];
            ++cnt;
        }
    }
    return 0;
}