14938번: 서강그라운드
예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을
www.acmicpc.net
플로이드 와샬 알고리즘을 이용하여 각 정점에서부터의 최단거리를 모두 구해줍니다.
그리고 1 ~ N정점을 시작점으로 다른 정점과의 거리가 M 이하인 경우만 아이템 수를 더해줍니다.
다 더했으면 최댓값을 갱신해줍니다.
|
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
|
#include <iostream>
#include <algorithm>
#define INF 1000000000
using namespace std;
int dis[101][101], list[101];
int N, M, R;
void solve() {
int ans = 0;
for (int i = 1; i <= N; i++) {
int sum = 0;
for (int j = 1; j <= N; j++) {
if (dis[i][j] > M) continue;
sum += list[j];
}
ans = max(ans, sum);
}
cout << ans << '\n';
}
void func() {
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++){
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
}
void init() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i == j) dis[i][j] = 0;
else dis[i][j] = INF;
}
}
}
void input() {
int u, v, w;
cin >> N >> M >> R;
init();
for (int i = 1; i <= N; i++) {
cin >> list[i];
}
while (R--) {
cin >> u >> v >> w;
dis[u][v] = w;
dis[v][u] = w;
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
solve();
return 0;
}
|
cs |
'algorithm > Floyd' 카테고리의 다른 글
| boj 2273 줄 서기 (0) | 2021.04.16 |
|---|