1. 접근 방법
- 처음엔 DFS 또는 BFS로 접근
- 근데 해보니 이전에 왔던 것보다 적은 거리를 써서온건 보내고, 보낸 다음부터 이어지는 건 겹치면 빼야함.
- 결국 플로이드워셜로 최소거리를 모두 구한 후, 탐색범위 안에 들어오는 지역의 아이템을 모두 더하는 방식과 동일함.
코드
#include <iostream>#include <list>#include <cstring>using namespace std;int n, m, r, t, item[31], area[31][31];int check[31];list<pair<int, pair<int, int>>> q;int floyd();int max(int a, int b) { return a > b ? a : b;}int min(int a, int b) { return a < b ? a : b;}int main() { cin >> n >> m >> r; for (int i = 1; i <= n; i++) cin >> item[i]; for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) if (i != j) area[i][j] = 200000000; for (int i = 0; i < r; i++) { int a, b, c; cin >> a >> b >> c; if (c < area[a][b]) { area[a][b] = c; area[b][a] = c; } } cout << floyd() << endl;}int floyd() { int result = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= n; k++) { if (area[j][k] > area[j][i] + area[i][k]) area[j][k] = area[j][i] + area[i][k]; } } } for (int i = 1; i <= n; i++) { int temp = 0; for (int j = 1; j <= n; j++) { if (area[i][j] <= m) temp += item[j]; } result = max(result, temp); } return result;}