14950 정복자

다익스트라 문제다.

시작 도시는 추가비용이 0

1번째 도시는 t

2번째 도시는 2t

...

이렇게 증가한다.

결국 n개의 도시가 있다면

t + 2t + 3t + ... + (n-1)*t의 추가비용이 든다.

그리고 도시를 점령하는 순간 현재 뻗을 수 있는 모든 도로에 대해 비용이 증가되는 것이므로

미리 다 더해놓고 다익스트라를 돌리는 것과 같다.

#include <stdio.h>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
 
typedef pair<int, int> pii;
 
int main() {
    int n, m, t, ans, d[10001], u, v, w;
    vector<pii> adj[10001];
    memset(d, -1, sizeof(d));
    scanf("%d%d%d", &n, &m, &t);
    while (m--) {
        scanf("%d%d%d", &u, &v, &w);
        adj[u].push_back({ v,w });
        adj[v].push_back({ u,w });
    }
    priority_queue<pii> q;
    q.push({ 0,1 });
    ans = t*(n - 2)*(n - 1) / 2;
    while (q.size()) {
        int c = -q.top().first;
        int x = q.top().second;
        q.pop();
        if (d[x] != -1) continue;
        d[x] = c;
        ans += c;
        for (auto i : adj[x]) {
            if (d[i.first] != -1) continue;
            q.push({ -i.second, i.first });
        }
    }
    printf("%d", ans);
    return 0;
}