10715번: JOI 공원

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


$O(mlgn)$

초기 s=모든 간선 합
다익스트라 알고리즘을 돌리면서 선택된 정점에 인접한 정점 중, 이미 최단거리를 구한 정점과 연결하는 비용을 s에서 뺀다.
이 때, (선택된 정점까지의 최단거리)*c+s가 정비 비용이다.
다익스트라 알고리즘을 마칠 때까지 모든 선택 정점에 대해 정비 비용을 구하고 그 중 최솟값을 출력한다.

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5;
int n, m, c, ck[MAX_N + 1];
vector<pair<int, int> > adj[MAX_N + 1];
ll r = 1e15, s;
int main() {
    scanf("%d %d %d", &n, &m, &c);
    for (int i = 0, x, y, z; i < m; i++) {
        scanf("%d %d %d", &x, &y, &z);
        adj[x].push_back({ y,z });
        adj[y].push_back({ x,z });
        s += z;
    }
    priority_queue<pair<ll, int> > pq;
    pq.push({ 0,1 });
    while (!pq.empty()) {
        int h = pq.top().second;
        ll tdis = -pq.top().first;
        pq.pop();
        if (ck[h]) continue;
        ck[h] = 1;
        for (auto it : adj[h]) {
            if (ck[it.first]) s -= it.second;
            pq.push({ -tdis - it.second,it.first });
        }
        r = min(r, s + tdis*c);
    }
    printf("%lld", r);
    return 0;
}