문제
풀이
- 모든 정점에서 모든 정점으로의 최단 거리가 필요하고 정점의 수가 적으므로 플로이드-워셜 알고리즘을 사용한다.
코드
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int n, m, r;
int graph[101][101];
void floydWarshall()
{
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
for (int k = 1; k <= n; ++k)
{
if (graph[j][i] != INT_MAX && graph[i][k] != INT_MAX)
{
graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k]);
}
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
vector<int> itemNum_node;
int answer = 0;
cin >> n >> m >> r;
// 노드 당 아이템 수 입력
for (int i = 0; i < n; ++i)
{
int temp;
cin >> temp;
itemNum_node.push_back(temp);
}
// 그래프 입력
fill(&graph[0][0], &graph[100][100], INT_MAX);
while (r--)
{
int n1, n2;
cin >> n1 >> n2;
cin >> graph[n1][n2];
graph[n2][n1] = graph[n1][n2];
}
for (int i = 1; i <= n; ++i)
{
graph[i][i] = 0;
}
floydWarshall();
for (int i = 1; i <= n; ++i)
{
int temp = 0;
for (int j = 1; j <= n; ++j)
{
// 경로가 m이하라면 아이템 수 추가 가능
if (graph[i][j] <= m)
{
temp += itemNum_node[j - 1];
}
}
answer = max(answer, temp);
}
cout << answer;
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준][C++] 2638: 치즈 (0) | 2023.10.02 |
---|---|
[백준][C++] 17144: 미세먼지 안녕! (0) | 2023.10.02 |
[백준][C++] 12851: 숨바꼭질 2 (0) | 2023.09.29 |
[백준][C++] 11054: 가장 긴 바이토닉 부분 수열 (0) | 2023.09.28 |
[백준][C++] 10830: 행렬 제곱 (0) | 2023.09.27 |