BOJ 14950, 정복자
ProblemSolving ·이 문제는 최소스패닝트리(MST)를 이용한 문제입니다. 저는 Prim 알고리즘을 이용해서 풀었습니다.
풀이
기본 Prim 알고리즘에 추가로 하나를 정복할때마다 가중치를 t씩 증가시켜주는 문제입니다.
어차피 모든 노드를 방문해야하므로 정복해야하는 숫자는 정해져있어 간단하게 해결할 수 있습니다.
add라는 변수에 t씩 더하면서 n-2번만큼 sum에 더해주면 됩니다!
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<string>
#include<iostream>
#include<stack>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
typedef long long ll;
vector<vector<pair<ll,ll>>> v(10001);
priority_queue <pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
ll n, m, t, chk[10001], sum, add;
void Prim(ll st)
{
pq.push({ 0,1 });
while (!pq.empty())
{
ll cost = pq.top().first;
ll here = pq.top().second;
pq.pop();
if (chk[here]==1) continue;
chk[here] = 1;
sum += cost;
for (ll i = 0; i < v[here].size(); i++)
{
ll next = v[here][i].first;
ll nextcost = v[here][i].second;
if (chk[next]==0)
pq.push({nextcost, next});
}
}
}
int main() {
scanf("%lld %lld %lld", &n, &m, &t);
for (ll i = 1; i <= m; i++)
{
ll a, b, c;
scanf("%lld %lld %lld", &a, &b, &c);
v[a].push_back({ b,c });
v[b].push_back({ a,c });
}
Prim(1);
for (ll i = 1; i <= n - 2; i++)
{
add += t;
sum += add;
}
printf("%lld", sum);
return 0;
}