2398번: 3인통화 - 최적화 필요

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

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int MAX_N = 1e3;
int n, m, s[3], dist[3][MAX_N + 1], from[3][MAX_N + 1];
vector<pair<int, int>> adj[MAX_N + 1];
void spath(int idx) {
    priority_queue<pair<int, int>> pq;
    fill(dist[idx] + 1, dist[idx] + 1 + n, 2e9);
    dist[idx][s[idx]] = 0;
    from[idx][s[idx]] = -1;
    pq.push({ 0,s[idx] });
    while (!pq.empty()) {
        int h = pq.top().second, dis = -pq.top().first;
        pq.pop();
        if (dist[idx][h] != dis) continue;
        for (auto t : adj[h]) {
            if (dist[idx][t.first] > dis + t.second) {
                dist[idx][t.first] = dis + t.second;
                from[idx][t.first] = h;
                pq.push({ -dist[idx][t.first],t.first });
            }
        }
    }
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        adj[a].push_back({ b,c });
        adj[b].push_back({ a,c });
    }
    scanf("%d %d %d", &s[0], &s[1], &s[2]);
    spath(0); spath(1); spath(2);
    int mini = 2e9, pos;
    for (int i = 1; i <= n; i++) {
        if (mini > dist[0][i] + dist[1][i] + dist[2][i]) {
            mini = dist[0][i] + dist[1][i] + dist[2][i];
            pos = i;
        }
    }
    vector<pair<int, int>> path;
    for (int i = 0; i < 3; i++)
        for (int j = pos; from[i][j] != -1; j = from[i][j])
            path.push_back({ j,from[i][j] });
    printf("%d %d\n", mini, path.size());
    for (auto it : path) printf("%d %d\n", it.first, it.second);
    return 0;
}