[1197] 최소 스패닝 트리

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

1197번: 최소 스패닝 트리

<문제>

MST 기본문제, 크루스칼이나 프림을 구현하면 해결할 수 있다.

 

<소스코드>

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
#include<limits.h>
using namespace std;
int v, e;
const int INF = INT_MAX;
vector <pair<int, int> >adj[10003];
bool visit[10003];
int dist[10003];
long long prim(void) {
    int i, j, cur = 0, min_dist = INF;
    long long sum = 0;
    for (int i = 1; i <= v; i++) {
        dist[i] = INF;
        visit[v] = false;
    }
    dist[1] = 0;
    for (i = 1; i <= v; i++) {
        cur = -1;
        min_dist = INF;
        for (j = 1; j <= v; j++) {
            if (visit[j] == false && dist[j] < min_dist) {
                min_dist = dist[j];
                cur = j;
            }
        }
        if (cur == -1)return (long long)INF;
        sum += min_dist;
        visit[cur] = true;
        for (auto edge : adj[cur])
            dist[edge.first] = min(dist[edge.first], edge.second);
    }
    return sum;
}
int main(void) {
    int i;
    scanf("%d %d", &v, &e);
    for (i = 0; i < e; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        adj[a].push_back(make_pair(b, c));
        adj[b].push_back(make_pair(a, c));
    }
    printf("%lld", prim());
    return 0;
}

프림알고리즘을 통해 해결하였다.