[백준 14938] 서강그라운드

1. 문제이해

최단거리를 구해서 조건에 맞게 값을 출력하는 문제

모든 정점에 대해 알아봐야하기 때문에 다익스트라를 n번 하거나 플로이드와샬을 하면 됐다.

n^3을 해도 1000000밖에 되지 않아 1초에 들어오기 때문에 플로이드와샬로 문제를 풀었다.

 

연결되어 있는 것 중

수색범위가 m 이하

얻을 수 있는 아이템이 최대인 것을 출력 ! 

 

2. 풀이

#include <iostream>
#include <vector>
using namespace std;

#define INF 100000000
#define MAX 101
int n, m, r, a, b, c;
int dist[MAX][MAX];
vector<int> items;
int maxRes = 0;

int main() {
    cin >> n >> m >> r;

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

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

    for (int i = 0; i < r; i++) {
        cin >> a >> b >> c;
        if (dist[a][b] > c) {
            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 (dist[i][k] == INF || dist[k][j] == INF) {
                    continue;
                }
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    dist[j][i] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        int sum = 0;

        for (int j = 1; j <= n; j++) {
            if (dist[i][j] <= m) {
                sum += items[j];
            }
        }
        if (sum > maxRes) {
            maxRes = sum;
        }
    }

    cout << maxRes;
    return 0;
}