BOJ 14938 : 서강그라운드 [C++]

문제

14938번: 서강그라운드

 

다익스트라를 각 노드 별로 수행해서 해결해야하나 했다가,

인접 매트릭스를 쓰면 될 것 같아 코드를 작성하다 실패.

인접 매트릭스를 활용한 최단거리 알고리즘이 플로이드 워셜이란걸 검색해서 알아내 이걸로 해결

 

#include <iostream>

#define MAX_DIST 1501

int items[101] = {0, };
int max_items = 0;
int adj_mat[101][101];

void sol(int n, int m) {
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < n + 1; j++) {
            for (int k = 1; k < n + 1; k++) {
                if (adj_mat[j][i] != MAX_DIST && adj_mat[i][k] != MAX_DIST) {
                    if (adj_mat[j][k] > adj_mat[j][i] + adj_mat[i][k]) {
                        adj_mat[j][k] = adj_mat[j][i] + adj_mat[i][k];
                    }
                }
            }
        }
    }

    for (int i = 1; i < n + 1; i++) {
        int possible_items = 0;
        for (int j = 1; j < n + 1; j++) {
            if (adj_mat[i][j] <= m) {
                possible_items += items[j];
            }
        }
        if (possible_items > max_items) {
            max_items = possible_items;
        }
    }
}

int main() {
    int n = 0, m = 0, r = 0;
    std::cin >> n >> m >> r;

    for (int i = 1; i < n + 1; i++) {
        std::cin >> items[i];
    }

    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < n + 1; j++) {
            if (i == j) {
                adj_mat[i][j] = 0;
            } else {
                adj_mat[i][j] = MAX_DIST;
            }
        }
    }

    for (int i = 0; i < r; i++) {
        int a = 0, b = 0, len = 0;
        std::cin >> a >> b >> len;
        adj_mat[a][b] = len;
        adj_mat[b][a] = len;
    }

    sol(n, m);

    std::cout << max_items << "\n";

    return 0;
}