그래프 문제이다.
지역(노드)이 n개 있고, 각 노드마다 value가 있다. 양방향 그래프로 weight가 있다.
수색할 수 있는 최대 weight가 존재할 때, 얼마나 노드의 value를 최대로 탐색할 수 있는지 묻는 문제이다.
플로이드-와샬 알고리즘으로 모든 점 최단경로를 구한다. 최대 사이즈가 100이므로 3승을 해도 1초인 1억회 연산을 수행하지 않는다. 그러므로 사용해도 되는 알고리즘이다.
그 후 1번 노드부터 n번 노드까지 모든 노드의 최단경로를 탐색해서 수색 비용보다 작다면 value를 모두 합해서 vector에 삽입한다.
그 후 vector의 최대값을 정답으로 출력한다.
#include <bits/stdc++.h>
using namespace std;
int n, m, r;
int cost[101][101];
int item[101];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
for (int i = 0; i < 101; i++)
for (int j = 0; j < 101; j++)
cost[i][j] = INT_MAX;
cin >> n >> m >> r;
for (int i = 1; i <= n; i++)
{
cin >> item[i];
}
for (int i = 1; i <= r; i++)
{
int a, b, l;
cin >> a >> b >> l;
cost[a][b] = min(cost[a][b], l);
cost[b][a] = min(cost[b][a], l);
}
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (cost[i][k] == INT_MAX || cost[k][j] == INT_MAX)
continue;
cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
}
}
}
for (int i = 1; i <= n; i++)
{
cost[i][i] = 0;
}
vector<int> v;
for (int i = 1; i <= n; i++)
{
int sum = 0;
for (int j = 1; j <= n; j++)
{
if (cost[i][j] <= m)
sum += item[j];
}
v.push_back(sum);
}
sort(v.begin(), v.end(), greater<int>());
cout << v[0];
return 0;
}
플로이드-와샬 알고리즘의 틀을 이해하자
for (k : 1 ~ n)
for (i : 1 ~ n)
for (j : 1 ~ n)
if (cost[i][k] == INT_MAX || cost[k][j] == INT_MAX)
continue;
if (cost[i][j] > cost[i][k] + cost[k][j])
cost[i][j] = cost[i][k] + cost[k][j]