본문 바로가기

알고리즘 관련/BOJ

BOJ)14938 서강그라운드

문제: icpc.me/14938


n의 범위가 작고 다대다 최단거리를 필요로 하기 때문에 플로이드 워셜 알고리즘을 사용할 수 있다.

플로이드 워셜 알고리즘으로 모든 정점쌍의 최단거리를 구해준 후 , 모든 정점을 기준으로 얻을 수 있는 아이템의 개수를 세준 뒤 그 중에 최댓값을 출력해주면 된다.


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
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, m, r, item[111], a[111][111], res;
int main() {
    memset(a, 0x3fsizeof(a));
    scanf("%d%d%d"&n, &m, &r);
    for (int i = 1; i <= n; i++)
        scanf("%d"&item[i]);
    for (int i = 0; i < r; i++) {
        int x, y, z;
        scanf("%d%d%d"&x, &y, &z);
        a[x][y] = min(a[x][y], z);
        a[y][x] = min(a[y][x], z);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                if (j == k)
                    a[j][k] = 0;
                a[j][k] = min(a[j][k], a[j][i] + a[i][k]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        int curr = 0;
        for (int j = 1; j <= n; j++) {
            if (a[i][j] <= m)
                curr += item[j];
        }
        res = max(res, curr);
    }
    printf("%d\n", res);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)15270 친구 팰린드롬  (0) 2017.12.05
BOJ)14939 불 끄기  (0) 2017.12.04
BOJ)14936 엘리베이터 장난  (0) 2017.12.04
BOJ)11670 초등 수학  (0) 2017.11.15
BOJ)3136 평면도  (0) 2017.11.15