ALGORITHM/BOJ
[BOJ] 14938 서강그라운드
0298
2022. 6. 26. 22:31
https://www.acmicpc.net/problem/14938
14938번: 서강그라운드
예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을
www.acmicpc.net
2022-06-26
|
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
|
import java.util.Arrays;
import java.util.Scanner;
public class Main14938 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int R = sc.nextInt();
int[] arr = new int[N+1];
for(int i = 1; i <= N; i++) arr[i] = sc.nextInt();
int[][] dist = new int[N+1][N+1];
for(int[] i: dist) Arrays.fill(i, 987654321);
for(int i = 0; i < R; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
dist[a][b] = c;
dist[b][a] = c;
}
for(int k = 1; k <= N; k++) {
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++) {
if(i == j) continue;
if(dist[i][j] > dist[i][k] + dist[k][j]) dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
int answer = 0;
for(int i = 1; i <= N; i++) {
int item = arr[i];
for(int j = 1; j <= N; j++) {
if(dist[i][j] != 987654321 && dist[i][j] <= M) {
item += arr[j];
}
}
answer = Math.max(answer, item);
}
System.out.println(answer);
}
}
|
cs |
#문제풀이
플로이드 와샬로 문제이다. 모든 정점에서 모든 정점까지 다 구한 후 마지막에 수색 범위 M이하 짧은 길이의 아이템 수를 더해서 가장 큰 값을 출력하면 된다.
