-
Notifications
You must be signed in to change notification settings - Fork 2
/
14938_josueyeon.cpp
73 lines (61 loc) · 1.46 KB
/
14938_josueyeon.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// shortest path: 플로이드 워셜(N:N)
// 아이템까지의 최단 거리를 구해서 수색 범위 내에 있는 아이템의 총합이 가장 큰 것을 반환
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int graph[101][101];
int item[31];
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
// n(지역 개수), m(수색 범위), r(길의 개수)
int n, m, r;
cin>>n>>m>>r;
for(int i = 1;i <= 101;i++)
{
for(int j = 1;j <= 101;j++)
{
if (i == j)
graph[i][j] = 0;
else
graph[i][j] = 1e9;
}
}
// 구역에 있는 아이템의 수
for(int i = 1;i <= n;i++)
cin>>item[i];
for(int i = 0;i < r;i++)
{
int a, b, c;
cin>>a>>b>>c;
graph[a][b] = c;
graph[b][a] = c;
}
// 플로이드 워셜 탐색 진행
for(int i = 1;i <= n;i++)
{
for(int a = 1;a <= n;a++)
{
for(int b = 1;b <= n;b++)
{
graph[a][b] = min(graph[a][b], graph[a][i] + graph[i][b]);
}
}
}
int result = 0;
for(int i = 1;i <= n;i++)
{
int sum = 0;
for(int j = 1;j <= n;j++)
{
if (graph[i][j] <= m)
sum += item[j];
}
result = max(sum, result);
}
cout<<result<<"\n";
return 0;
}