백준 14938번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	128MB	골드 4

---

풀이

 이 문제 역시 최단경로 문제이다. 다만, 특정 정점을 시작점으로 잡는 것이 아니라 임의의 정점에서 시작했을 때, 수색 범위 내에 있는 아이템의 개수의 최댓값을 구하는 문제이다. 정점의 개수도 그렇고 간선의 개수도 모두 100 이하이기 때문에 모든 정점에서 다익스트라를 돌려도 되겠으나, 정점의 개수가 적기 때문에 플로이드워셜로 한번에 최단 거리를 구한 후, 각 정점에 대해 순회하며 최댓값을 구했다.

코드

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

vector<vector<int>> graph;
vector<int> item;
int n, m;

void input() {
	int area1, area2, dist, r;
	cin >> n >> m >> r;
	graph.resize(n + 1, vector<int>(n + 1, 123456));
	item.resize(n + 1);

	for(int i = 0; i <= n; i++) graph[i][i] = 0;
	for(int i = 1; i <= n; i++) cin >> item[i];
	while(r--) {
		cin >> area1 >> area2 >> dist;
		graph[area1][area2] = dist;
		graph[area2][area1] = dist;
	}
}

void sol() {
	int ans = 0, temp;

	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]);
			}
		}
	}

	for(int row = 1; row <= n; row++) {
		temp = 0;
		for(int col = 1; col <= n; col++) {
			if (graph[row][col] <= m) {
				temp += item[col];
			}
		}
		ans = max(ans, temp);
	}

	cout << ans;
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	input();
	sol();
}