BOJ)14938 서강그라운드

문제: icpc.me/14938

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

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

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, m, r, item[111], a[111][111], res;
int main() {
    memset(a, 0x3f, sizeof(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;
}