글 읽기 - 제가 놓친 부분이 있을까요??

persona_k 4년 전 1

플로이드 워셜을 쓰고 나서,

각 정점마다 ans 배열에 가장 큰 점수로 저장하면서, 전체 정점 중 가장 작은 점수를 point에 저장합니다.

ans 배열을 돌면서 point와 같은 사람은 cnt++하고, 그 사람을 출력합니다.

어떤 부분을 놓쳤을까요?

#include <iostream>
#include <algorithm>
#include <vector>

#define MAX 52
#define INF 210000000;

using namespace std;

int d[MAX][MAX];
int ans[MAX];
int n;

void setInf() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			d[i][j] = INF;
		}
	}
}

void floydWarshall() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (d[i][k] + d[k][j] < d[i][j])
					d[i][j] = d[i][k] + d[k][j];
			}
		}
	}
}

int main()
{
	cin >> n;
	setInf();
	while (1) {
		int u, v;
		cin >> u >> v;

		if (u == -1 && v == -1) break;

		d[u][v] = d[v][u] = 1; //양방향
	}

	floydWarshall();

	int mx = 0, point = INF;
	for (int i = 1; i <= n; i++) {
		mx = 0;
		for (int j = 1; j <= n; j++) {
			if (mx < d[i][j]) mx = d[i][j];
		}
		ans[i] = mx;                //해당 정점의 가장 큰 점수로 저장
		point = min(point, ans[i]); //가장 작은 점수 갱신
	}

	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (ans[i] == point) //회장 후보의 수
			cnt++;
	}
	cout << point << ' ' << cnt << endl;
	for (int i = 1; i <= n; i++) {
		if (ans[i] == point) {
			cout << i << ' '; //회장 후보의 정점 출력
		}
	}

	return 0;
}

persona_k 4년 전 1

해결했습니다!

문제는 자기 자신으로 도는 정점은 0으로 냅두어야 됩니다.

즉 d[i][i] = 0으로,

저는 무한대로 초기화를 해서 틀렸네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

제가 놓친 부분이 있을까요??

persona_k 4년 전 1

persona_k 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말