나만 안되는 연애 (feat. 백준, 14621번)

나만 안되는 연애
https://www.acmicpc.net/problem/14621

14621번: 나만 안되는 연애

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
char school_type[1001]{0};                  // 학교 종류
bool visit[1001]{false};
vector<pair<int, int>> arr[1001];           // 다음 학교 번호, 거리
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;      // 거리, 다음 학교 번호
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, M, ans = 0, cnt = 0, next, nnext, dist;
    cin >> N >> M;
    for(register int n = 1; n <= N; ++n)
        cin >> school_type[n];
    for(register int m = 0, u, v, d; m < M; ++m){
        cin >> u >> v >> d;
        arr[u].push_back(make_pair(v, d)), arr[v].push_back(make_pair(u, d));
    }
    q.push(make_pair(0, 1));
    while(!q.empty()){
        dist = q.top().first, next = q.top().second; q.pop();
        if(visit[next])
            continue;
        visit[next] = true;
        ans += dist;
        if(++cnt == N){     // 연결된 학교수가 제공된 학교수와 같으면 종료
            cout << ans;
            return 0;
        }
        for(auto& v : arr[next]){
            nnext = v.first, dist = v.second;
            if(!visit[nnext] && school_type[next] != school_type[nnext])
                q.push(make_pair(dist, nnext));
        }
    }
    cout << -1;
	return 0;
}
// *&)*@*

 

반응형

최소 스패닝 트리를 구하는 문제입니다.

저는 프림 알고리즘을 사용하여 풀이하였습니다.

일반적인 MST와 다른 점이 있다면 거리를 연산하는 총 횟수가 제공된 학교수와 같을때 종료시켜야 한다는 점입니다.