문제 출처

1. 문제설명

  • N개의 정점과 M개의 간선으로 이뤄진 그래프가 있다.
  • 정점을 지날 시 아이템 t개를 얻을 수 있다.
    • 단, 간선의 비용이 m보다 작을 경우만 얻을 수 있다.

  • 다시 말해, i번 정점에서 출발했을 때, 비용이 m보다 작은 모든 아이템의 수를 계산하고, 얻을 수 있는 아이템의 최대값을 구하면 된다.

  • 문제 분류
    • Graph, Floyd


2. 알고리즘 설계

  • 플로이드-워셜 알고리즘 문제이다.
  • 문제를 보면, 무방향 그래프 이므로, u->v, v->u는 같은 비용을 갖는다.
  • 플로이드-워셜 값을 계산해주고,
  • 어떤 정점 i에서 시작했을 때 비용이 m을 넘지않는 값을 전부 더한다.
  • 이 값들 중 아이템의 수가 최대가 되는 값을 갱신해주면 된다.


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f, SZ = 102;
int n, m, r, T[SZ], ans, D[SZ][SZ];

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

	cin >> n >> m >> r;

	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			D[i][j] = (i==j ? 0 : INF);

	for(int i=1; i<=n; i++)
		cin >> T[i];

	for(int u, v, w; r--;) {
		cin >> u >> v >> w;
		D[v][u] = D[u][v] = min(D[u][v], w);
	}

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

	for(int i=1; i<=n; i++) {
		int cmp = T[i];
		for(int j=1; j<=n; j++) {
			if(D[i][j] == INF || D[i][j] == 0 || D[i][j] > m) continue;
			cmp += T[j];
		}
		ans = max(ans, cmp);
	}

	cout << ans;

	return 0;
}