9370번: Destination Unknown

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

각 목적지 후보마다 해당 지점까지의 최단 거리가 g와 h사이 도로를 거쳐가는 최단 거리와 같은지 판단하는 문제이다.
간단히 각 교차로마다 g와 h사이 도로를 지났는지의 여부에 따라 두 개의 노드를 만들어서 최단거리를 구해 비교하면 된다.

또는 노드를 두 개씩 만들지 않고 다음과 같은 트릭을 사용해서 풀 수도 있다.
1. 모든 도로의 길이를 2배로 만든다.
2. g와 h사이 도로 길이만 1 감소 시킨다.
3. 최단 경로를 구한 뒤, 후보 까지의 최단 거리가 홀수인 경우 목적지로 가능하다.

시간복잡도는 각 테스트 케이스마다 $O(m\lg n)$

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
void solve() {
    vector<pair<int, int> > adj[2001];
    int cst[2001], n, m, t, s, g, h, c[100];
    priority_queue<pair<int, int> > pq;
    scanf("%d%d%d%d%d%d", &n, &m, &t, &s, &g, &h);
    for (int i = 0, a, b, d; i < m; i++) {
        scanf("%d%d%d", &a, &b, &d);
        d *= 2;
        if (a*b == g*h&&a + b == g + h) d--;
        adj[a].push_back({ b,d });
        adj[b].push_back({ a,d });
    }
    fill(cst + 1, cst + 1 + n, 1e9);
    cst[s] = 0;
    pq.push({ 0,s });
    while (!pq.empty()) {
        int tdis = -pq.top().first, tpos = pq.top().second;
        pq.pop();
        if (tdis^cst[tpos]) continue;
        for (auto it : adj[tpos]) if (cst[it.first] > tdis + it.second) {
            cst[it.first] = tdis + it.second;
            pq.push({ -cst[it.first],it.first });
        }
    }
    for (int i = 0; i < t; i++) scanf("%d", c + i);
    sort(c, c + t);
    for (int i = 0; i < t; i++) if (cst[c[i]] & 1) printf("%d ", c[i]);
    puts("");
}
int main() {
    int T;
    for (scanf("%d", &T); T--;) solve();
    return 0;
}

9446번: Dwarf Tower

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

1. 다익스트라 알고리즘을 응용해서 풀 수 있다.
2. 현재까지 최소 비용을 구한 아이템 집합을 S라 하자.
3. 초기에는 제작 비용이 가장 싼 아이템이 S에 포함되어있다.
4. S이외의 아이템을 S로부터 제작 혹은 구매를 할 때 최소 비용과 해당 아이템을 각각 c, p라고 하자.
5. 앞으로 어떠한 방법을 사용해도 비용은 c보다 작을 수 없으므로 p를 만들기 위한 최소 비용은 c이다. 이 t를 S에 포함시킨다.
6. 이 그리디 알고리즘을 반복하면 각각의 아이템를 얻기위한 최소 비용을 모두 구할 수 있다.

시간복잡도는 $O((m+n)\lg(m+n))$

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int n, m, cost[10001];
priority_queue<pair<int, int> > pq;
vector<pair<int, int> > v[10001];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", cost + i), pq.push({ -cost[i],i });
    for (int i = 0, a, x, y; i < m; i++) {
        scanf("%d%d%d", &a, &x, &y);
        v[x].push_back({ y,a });
        v[y].push_back({ x,a });
    }
    while (!pq.empty()) {
        int c = -pq.top().first, p = pq.top().second;
        pq.pop();
        if (cost[p] ^ c) continue;
        cost[p] = c;
        for (auto it : v[p]) if (cost[it.second]>c + cost[it.first]) {
            cost[it.second] = c + cost[it.first];
            pq.push({ -cost[it.second],it.second });
        }
    }
    printf("%d", cost[1]);
    return 0;
}

1257번: 엄청난 부자

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


$\sum_{i=1}^n {A[i]*B[i]} = M (B[i]>=0)$을 만족할 때 $\sum_{i=1}^n {B[i]}$의 최댓값을 구하는 문제이다.
A[1..n]에서 A[n](=L)이 가장 크고 일단 B[n]<0이어도 된다고 하자.
어떤 k에 대해 $\sum_{i=1}^{n-1} {A[i]*B[i]} = k (mod L)$을 만족하는 $\sum_{i=1}^{n-1} {B[i]}$의 최솟값을 구해놓았다면 여기에 L짜리 동전을 x개 추가함으로써 $\sum_{i=1}^{n-1} {A[i]*B[i]} = Lx + k$ 꼴의 $\sum_{i=1}^n {B[i]}$ 최솟값을 모두 알아낼 수 있다.

문제는 x = $[M/L]$, k = M%L일 때를 구하는 것이다.

이를 이용하기 위해 L로 나눈나머지로 가능한 k = 0..L-1에 대한 노드를 만들고, 각 동전의 추가에 따라 간선을 추가한다.
i번 노드와 가치가 t인 동전에 대해
i+t < L인 경우, 단순이 t짜리 동전을 하나 추가한다는 의미에서 i -> i+t, 가중치 1인 간선을 만든다.
i+t >= L인 경우, L짜리 동전을 하나 없애고 t짜리 동전을 하나 추가한다는 의미에서 i -> i+t-L, 가중치 0인 간선을 만든다.
모든 노드와 간선을 만든 후 0에서 M%L까지의 최단 거리를 구한다. 이 값 + $[M/L]$이 답이다.

처음으로 돌아와서 B[n]<0인 경우가 과연 존재할까?
최단경로는 길어야 L-1이므로 M%L을 만들기 위해 제거한 L짜리 동전은 많아야 L-1개이다.
그런데 입력으로 주어지는 M은 10억 이상, L은 10000이하이므로 $[M/L] >= 10^6 > 9999 = L-1$.
고로 주어진 입력에 따라 본 알고리즘을 통해 구한 답은 항상 B[n]>=0이다.

아래 소스는 $O(nL\lg {nL})$

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
long long m;
int n, s, a[1000], dp[10000];
int main() {
    scanf("%lld%d", &m, &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    s = *max_element(a, a + n);
    for (int i = 1; i < s; i++) dp[i] = 1e9;
    priority_queue<pair<int, int> > pq;
    pq.push({ 0,0 });
    while (!pq.empty()) {
        int tdis = -pq.top().first, tpos = pq.top().second;
        pq.pop();
        if (dp[tpos] ^ tdis) continue;
        for (int i = 0; i < n; i++) {
            int t = tpos + a[i];
            if (dp[t%s] > tdis + 1 - t / s) {
                dp[t%s] = tdis + 1 - t / s;
                pq.push({ -dp[t%s],t%s });
            }
        }
    }
    printf("%lld", dp[m%s] + m / s);
    return 0;
}

14554번: The Other Way

https://www.acmicpc.net/source/5852286


$O(m\lg n)$

최단경로를 따라 DAG를 만들고 DP를 한다.

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int n, m, s, e, dp[MXN + 1];
long long dis[MXN + 1];
vector<pair<int, int> > adj[MXN + 1];
priority_queue<pair<long long, int> > pq;
int main() {
    scanf("%d%d%d%d", &n, &m, &s, &e);
    for (int i = 0, a, b, c; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        adj[a].push_back({ b,c });
        adj[b].push_back({ a,c });
    }
    fill(dis + 1, dis + 1 + n, 1e18);
    dis[s] = 0;
    dp[s] = 1;
    pq.push({ 0,s });
    while (!pq.empty()) {
        int tpos = pq.top().second;
        long long tdis = -pq.top().first;
        pq.pop();
        if (dis[tpos] ^ tdis) continue;
        for (auto it : adj[tpos]) {
            if (it.second + tdis < dis[it.first]) {
                dis[it.first] = it.second + tdis;
                dp[it.first] = 0;
                pq.push({ -dis[it.first],it.first });
            }
            if (it.second + tdis == dis[it.first]) dp[it.first] = (dp[it.first] + dp[tpos]) % (int(1e9) + 9);
        }
    }
    printf("%d", dp[e]);
    return 0;
}

10282번: Failing Components

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

$O(td\lg n)$

c로부터 도달 가능한 컴퓨터만 감염되며 최단 시간의 최댓값이 마지막 컴퓨터가 감염되는데 걸리는 시간이다.
아래는 다익스트라 알고리즘을 사용했다.

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int t, n, d, c;
int main() {
    scanf("%d", &t);
    while (t--) {
        vector<pair<int, int> > adj[10001];
        scanf("%d%d%d", &n, &d, &c);
        for (int i = 0, x, y, z; i < d; i++) {
            scanf("%d%d%d", &x, &y, &z);
            adj[y].push_back({ x,z });
        }
        int mini[10001], cnt = 0, t = 0;
        priority_queue<pair<int, int> > pq;
        fill(mini + 1, mini + 1 + n, 1e9);
        mini[c] = 0;
        pq.push({ 0,c });
        while (!pq.empty()) {
            int tpos = pq.top().second, tdis = -pq.top().first;
            pq.pop();
            if (mini[tpos] ^ tdis) continue;
            for (auto it : adj[tpos]) {
                if (mini[it.first] > tdis + it.second) {
                    mini[it.first] = tdis + it.second;
                    pq.push({ -mini[it.first],it.first });
                }
            }
        }
        for (int i = 1; i <= n; i++) if (mini[i] < 1e9) t = max(t, mini[i]), cnt++;
        printf("%d %d\n", cnt, t);
    }
    return 0;
}

12752번: Cities

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

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int MXN = 1e5;
typedef long long ll;
int n, k, m, a[6], p[5];
ll dis[6][MXN + 2], r = 1e15, cst[5][5][MXN + 1];
vector<pair<int, ll> > adj[MXN + 2];
void spath(int h) {
    fill(dis[h], dis[h + 1], 1e15);
    dis[h][a[h]] = 0;
    priority_queue<pair<ll, int> > pq;
    pq.push({ 0,a[h] });
    while (!pq.empty()) {
        int tpos = pq.top().second;
        ll tdis = -pq.top().first;
        pq.pop();
        if (tdis^dis[h][tpos]) continue;
        for (auto it : adj[tpos]) if (it.second + dis[h][tpos] < dis[h][it.first]) {
            dis[h][it.first] = it.second + dis[h][tpos];
            pq.push({ -dis[h][it.first],it.first });
        }
    }
}
int main() {
    scanf("%d%d%d", &n, &k, &m);
    for (int i = 0; i < k; i++) scanf("%d", a + i), p[i] = i;
    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 });
    }
    for (int i = 0; i < k; i++) spath(i);
    for (int i = 1; i <= n; i++) {
        adj[0].push_back({ i,0 });
        adj[i].push_back({ n + 1,0 });
        ll s = 0;
        for (int j = 0; j < k; j++) s += dis[j][i];
        r = min(r, s);
    }
    if (k > 3) {
        for (int i = 1; i < k; i++) {
            for (int j = 0; j < i; j++) {
                for (int u = 1; u <= n; u++) {
                    adj[0][u - 1].second = dis[i][u] + dis[j][u];
                    adj[u].rbegin()->second = 0;
                    for (int v = 0; v < k; v++) if (v^i&&v^j) adj[u].rbegin()->second += dis[v][u];
                }
                spath(k);
                r = min(r, dis[k][n + 1]);
                for (int u = 1; u <= n; u++) cst[i][j][u] = dis[k][u];
            }
        }
    }
    if (k == 5) {
        for (int i = 0; i < k; i++) {
            for (int p1 = 1; p1 < k; p1++) if (p1^i) {
                for (int p2 = 0; p2 < p1; p2++) if (p2^i) {
                    int q[2], qcnt = 0;
                    for (int u = 0; u < k; u++) if (u^i&&u^p1&&u^p2) q[qcnt++] = u;
                    for (int u = 1; u <= n; u++) r = min(r, cst[p1][p2][u] + cst[q[1]][q[0]][u] + dis[i][u]);
                }
            }
        }
    }
    printf("%lld", r);
    return 0;
}

2211번: 네트워크 복구

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


$O(m\lg n)$

1번 지점으로부터 나머지 지점까지의 shortest path로 이뤄진 DAG를 구한다.

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int MXN = 1e3;
int cst[MXN + 1], fr[MXN + 1], n, m;
vector<pair<int, int> > adj[MXN + 1];
int main() {
    scanf("%d%d", &n, &m);
    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 });
    }
    fill(cst + 2, cst + 1 + n, 1e9);
    priority_queue<pair<int, int> > pq;
    pq.push({ 0,1 });
    printf("%d\n", n - 1);
    while (!pq.empty()) {
        int h = pq.top().second, d = -pq.top().first;
        pq.pop();
        if (cst[h] ^ d) continue;
        if (fr[h]) printf("%d %d\n", fr[h], h);
        for (auto it : adj[h]) if (d + it.second<cst[it.first]) {
            cst[it.first] = d + it.second;
            fr[it.first] = h;
            pq.push({ -cst[it.first],it.first });
        }
    }
    return 0;
}

5944번: Apple Delivery

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

$O(C\lg P)$

답은 min((pb~pa1 최단 거리),(pb~pa2 최단 거리)) + (pa1~pa2 최단 거리)

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int MXP = 1e5;
int c, p, pb, pa1, pa2, dis[MXP + 1];
vector<pair<int, int> > adj[MXP + 1];
void spath(int s) {
    fill(&dis[1], &dis[p + 1], 1e9);
    dis[s] = 0;
    priority_queue<pair<int, int> > pq;
    pq.push({ 0,s });
    while (!pq.empty()) {
        int h = pq.top().second, d = -pq.top().first;
        pq.pop();
        if (dis[h] ^ d) continue;
        for (auto it : adj[h]) if (d + it.second < dis[it.first]) {
            dis[it.first] = d + it.second;
            pq.push({ -dis[it.first],it.first });
        }
    }
}
int main() {
    scanf("%d%d%d%d%d", &c, &p, &pb, &pa1, &pa2);
    for (int i = 0, x, y, z; i < c; i++) {
        scanf("%d%d%d", &x, &y, &z);
        adj[x].push_back({ y,z });
        adj[y].push_back({ x,z });
    }
    spath(pa1);
    int t = dis[pa2];
    spath(pb);
    printf("%d", min(dis[pa1], dis[pa2]) + t);
    return 0;
}

9988번: Roadblock

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


$O(n^3)$

먼저, 최단 경로를 구해 놓는다.
이 경로를 제외한 나머지 간선을 지연시키면 전체 그래프에서 최단 경로는 바뀌지 않는다.
따라서 최단 경로에 존재하는 각각의 간선을 지연시켜보며 최대 n번만 최단 경로를 구하면 된다.

#include<cstdio>
const int MXN = 250;
int n, m, adj[MXN + 1][MXN + 1], path[MXN + 1], tpath[MXN + 1];
int spath() {
    int dis[MXN + 1], ck[MXN + 1] = {};
    dis[1] = 0;
    for (int i = 2; i <= n; i++) dis[i] = 1e9;
    for (int j = 1; j < n; j++) {
        int pos, maxi = 1e9;
        for (int i = 1; i <= n; i++) if (!ck[i] && dis[i] < maxi) {
            maxi = dis[i];
            pos = i;
        }
        ck[pos] = 1;
        for (int i = 1; i <= n; i++) if (maxi + adj[pos][i] < dis[i]) {
            dis[i] = maxi + adj[pos][i];
            path[i] = pos;
        }
    }
    return dis[n];
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) adj[i][j] = 1e9;
    for (int i = 0, a, b, l; i < m; i++) {
        scanf("%d%d%d", &a, &b, &l);
        adj[a][b] = adj[b][a] = l;
    }
    int opt = spath(), maxi = 0;
    for (int i = 1; i <= n; i++) tpath[i] = path[i];
    for (int i = n; i ^ 1; i = tpath[i]) {
        adj[i][tpath[i]] *= 2; adj[tpath[i]][i] *= 2;
        int t = spath();
        if (t > maxi) maxi = t;
        adj[i][tpath[i]] /= 2; adj[tpath[i]][i] /= 2;
    }
    printf("%d", maxi - opt);
    return 0;
}

2307번: 도로검문

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


$O(m^2\lg m)$

각 간선을 제외시켜보며 얻은 최단 시간의 최댓값과 원래의 최단 시간 차를 구한다.

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int MXN = 1e4, MXM = 5e4;
int a[MXM], b[MXM], n, m, maxi;
vector<pair<int, int> > adj[MXN + 1];
int spath(int x, int y) {
    priority_queue<pair<int, int> > pq;
    int ck[MXN + 1] = {};
    pq.push({ 0,1 });
    while (!pq.empty()) {
        int h = pq.top().second, dis = -pq.top().first;
        pq.pop();
        if (h == n) return dis;
        if (ck[h]) continue;
        ck[h] = 1;
        for (auto it : adj[h]) if (x + y^h + it.first || x*y^h*it.first)
            pq.push({ -it.second - dis,it.first });
    }
    return 1e9;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, t; i < m; i++) {
        scanf("%d%d%d", a + i, b + i, &t);
        adj[a[i]].push_back({ b[i],t });
        adj[b[i]].push_back({ a[i],t });
    }
    for (int i = 0; i < m; i++) maxi = max(maxi, spath(a[i], b[i]));
    printf("%d", maxi < 1e9 ? maxi - spath(0, 0) : -1);
    return 0;
}

추가로 모든 간선을 제외하면서 최단 시간을 m번이나 구할 필요는 없다.
처음에 최단 시간을 만드는 경로를 구하자.
이 경로상의 간선을 제외하지 않는다면 그대로 최단 경로를 이용하면 되므로 지연시간은 0이 된다.
따라서 최단 경로 상의 최대 n개 간선 각각을 제외해보며 지연 시간을 따져주면 된다.
이 방법의 전체 시간복잡도는 $O(nm\lg n)$

1162번: 도로포장

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


$O(km\lg n)$

k번째 최단 경로를 구하는 방법과 비슷하게 푼다.

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int MXN = 1e4, MXK = 20;
int n, m, k, ck[MXN*(MXK + 1)];
vector<pair<int, int> > adj[MXN];
priority_queue<pair<long long, int> > pq;
int main() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0, x, y, z; i < m; i++) {
        scanf("%d %d %d", &x, &y, &z);
        adj[x - 1].push_back({ y - 1,z });
        adj[y - 1].push_back({ x - 1,z });
    }
    pq.push({ 0,0 });
    while (!pq.empty()) {
        int h = pq.top().second;
        long long dis = -pq.top().first;
        pq.pop();
        if (h >= n*k + n || ck[h]) continue;
        if (h%n == n - 1) {
            printf("%lld", dis);
            break;
        }
        ck[h] = 1;
        for (auto it : adj[h%n]) pq.push({ -dis - it.second, it.first + h / n*n }), pq.push({ -dis, it.first + (h / n + 1)*n });
    }
    return 0;
}

10853번: Change of Scenery

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


$O(m\lg n)$

최단 경로의 개수를 세어 2개 이상이면 가능하고 아니면 불가능하다.

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int n, m, k, cst[10001], cnt[10001];
vector<pair<int, int> > adj[10001];
priority_queue<pair<int, int> > pq;
int main() {
    scanf("%d%d%d", &n, &m, &k);
    while (k--) scanf("%*d");
    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 });
    }
    fill(cst + 2, cst + 1 + n, 1e9);
    pq.push({ 0,1 }); cnt[1] = 1;
    while (!pq.empty()) {
        int h = pq.top().second, dis = -pq.top().first;
        pq.pop();
        if (cst[h] ^ dis) continue;
        if (cnt[h] > 2) cnt[h] = 2;
        for (auto it : adj[h]) {
            int tdis = it.second + dis;
            if (tdis < cst[it.first]) {
                cst[it.first] = tdis;
                cnt[it.first] = 0;
                pq.push({ -tdis,it.first });
            }
            if (tdis == cst[it.first]) cnt[it.first] += cnt[h];
        }
    }
    puts(cnt[n] - 1 ? "yes" : "no");
    return 0;
}

2176번: 합리적인 이동경로

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


$O(m\lg n)$

2번 정점을 시작 지점으로 다익스트라 알고리즘을 이용하면 거리가 최소인 지점을 차례대로 들를 수 있게 된다.
x번 정점을 탐색하고 있다면 x번보다 도착 지점(=2)에 가까운 거리의 정점에서 출발하는 경로 개수는 모두 구해놓았기 때문에 이를 이용하여 x번 정점에서 출발하는 경로 개수도 구할 수 있다.
답은 1번 정점에서 출발하는 경로 개수이다.

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int n, m, dp[1001], cst[1001];
vector<pair<int, int> > adj[1001];
priority_queue<pair<int, int> > pq;
int main() {
    scanf("%d%d", &n, &m);
    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 });
    }
    fill(cst + 1, cst + 1 + n, 0x7fffffff);
    cst[2] = 0; dp[2] = 1;
    pq.push({ 0,2 });
    while (!pq.empty()) {
        int h = pq.top().second, dis = -pq.top().first;
        pq.pop();
        if (cst[h] ^ dis) continue;
        for (auto it : adj[h]) {
            int tdis = it.second + dis;
            if (tdis < cst[it.first]) cst[it.first] = tdis, pq.push({ -tdis,it.first });
            if (cst[it.first] < dis) dp[h] += dp[it.first];
        }
    }
    printf("%d", dp[1]);
    return 0;
}

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;
}