백준 14938 서강그라운드 (c++) : 피너클

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

14938번: 서강그라운드

플로이드 와샬 문제다.

int item[101];
int graph[101][101];
int n, m, r;

item에는 각 구역의 아이템 개수

graph에는 구역이 어떻게 연결되어있는지가 들어간다.

cin >> n >> m >> r;
for (int i = 0; i < 101; i++)
	for (int j = 0; j < 101; j++) {
		graph[i][j] = 987654321;
		if (i == j) graph[i][j] = 0;
	}

n과 m과 r을 입력받은 뒤 graph를 초기화한다.

초기화 할때는 절대로 나올수 없는 큰수로 초기화 하고 만약 i와 j가 같다면 0으로 초기화한다.

for (int i = 1; i <= n; i++) cin >> item[i];
for (int i = 0; i < r; i++) {
	int a, b, c;
	cin >> a >> b >> c;
	graph[a][b] = c;
	graph[b][a] = c;
}

그후 item과 graph를 입력받는다.

graph는 양방향 통행이 가능하니 양쪽다 넣어준다.

for (int k = 1; k <= n; k++) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
		}
	}
}

이제 플로이드 와샬을 돌려주면 된다.

솔직히 플로이드 와샬 관련해서 인터넷에 좋은 블로그가 너무 많다.

내가 설명하는 것보다 그런 블로그를 보는것이 더욱 도움될것이다.

이 문제에서 주의해야할점은 반복문을 0부터 시작하는 것이 아니라 1부터 시작해야한다는 것이다.

int ans = -1;
for (int i = 1; i <= n; i++) {
	int sam = 0;
	for (int j = 1; j <= n; j++) {
		if (graph[i][j] <= m) {
			sam += item[j];
		}
	}
	ans = max(ans, sam);
}
cout << ans << endl;

이제 답을 구하면 끝이다.

모든 그래프를 돌아보며 거리가 m보다 작다면 sam에 더한뒤

만약 sam이 ans보다 크다면 ans를 업데이트 해준다.

전부 돌린뒤 ans를 출력하면 끝이다.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int item[101];
int graph[101][101];
int n, m, r;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m >> r;
	for (int i = 0; i < 101; i++)
		for (int j = 0; j < 101; j++) {
			graph[i][j] = 987654321;
			if (i == j) graph[i][j] = 0;
		}

	for (int i = 1; i <= n; i++) cin >> item[i];
	for (int i = 0; i < r; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a][b] = c;
		graph[b][a] = c;
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
			}
		}
	}


	int ans = -1;
	for (int i = 1; i <= n; i++) {
		int sam = 0;
		for (int j = 1; j <= n; j++) {
			if (graph[i][j] <= m) {
				sam += item[j];
			}
		}
		ans = max(ans, sam);
	}
	cout << ans << endl;
}

전체코드다.