글 읽기 - 어디 부분이 틀린걸까요? (다익스트라)

lyzqm 6년 전 0

모든 대학들은 연결되어야 하기때문에 정점1을 시작지점으로 잡고

다익스트라를 돌려서 dist[next]에 저장했습ㄴ다

그 후에 bfs를 돌려서 dist[next] == dist[here]+edge[here][next] 인 지점들에 대해서만 거리를 더했습니다.

모든대학이 연결안된경우도 체크했는데 어디서 틀린걸까요 ? ㅠㅠ

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
typedef pair<int, int> MP;
#define mp(a,b) make_pair(a,b)
#define INF 987654321
int N, M;
char gender[1001];
int dist[1001];
vector<MP> adj[1001];
void di(int start){
	priority_queue<MP, vector<MP>, greater<MP>> pq;

	fill(dist, dist + N + 1, INF);
	dist[start] = 0;
	pq.push(mp(0, start));

	while (!pq.empty()){
		int here = pq.top().second;
		int cost = pq.top().first;
		pq.pop();
		
		for (auto n : adj[here]){
			int next = n.second;
			if (gender[here] == gender[next]) continue;
			if (dist[next] > cost + n.first){
				dist[next] = cost + n.first;
				pq.push(mp(dist[next], next));
			}
		}
	}
}
int bfs(int start){
	for (int n = 1; n <= N; n++)
		if (dist[n] == INF) 
			return -1;

	bool visit[1001];
	int ans = 0;
	queue<MP> q;

	fill(visit, visit + N + 1, false);
	q.push(mp(0, start));
	visit[start] = true;
	while (!q.empty()){
		int here = q.front().second;
		int cost = q.front().first;
		q.pop();

		for (auto n : adj[here]){
			int next = n.second;
			if (gender[here] == gender[next] || visit[next]) continue;
			if (dist[next] == cost + n.first){
				visit[next] = true;
				q.push(mp(dist[next], next));
				ans += n.first;
			}
		}
	}
	return ans;
}
int main(){
	scanf("%d%d", &N, &M);
	for (int n = 1; n <= N; n++)
		scanf(" %c", &gender[n]);
	for (int m = 0; m < M; m++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		adj[a].push_back(mp(c, b));
		adj[b].push_back(mp(c, a));
	}
	const int start = 1;
	di(start);			//다익스트라 1에서 시작
	printf("%d\n", bfs(start));		// 1에서 bfs를 돌리며 거리 저장	
	return 0;
}