백준14938 - 서강그라운드

https://www.acmicpc.net/problem/14938

14938번: 서강그라운드

플로이드 와샬을 이용하여 풀었다. n개의 마을이 주어지고 서로 도달할 수 있는 비용이 주어져 있는 상태이기 때문에 플로이드 와샬을 수행하여 서로 도달하기 위하여 필요한 비용을 구하였다. 비용을 구한 후 각 마을을 기점으로 최대로 쓸 수 있는 비용보다 작은 경로를 찾아서 아이템의 수를 더하여 가장 많은 아이템을 먹을 수 있는 마을을 찾아서 출력하면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 101
using namespace std;

int n, m, r; //n개 마을, m개의 최대 비용, r개의 길의 갯수
int a, b, l; //a에서 b까지 비용 l이 든다.
int d[MAX][MAX] = {0,}; //플로이드 와샬 결과
int item[MAX] = {0, }; //각 마을의 아이템 갯수
int ans = -1; //답

//플로이드 와샬 수행
void floydWashall() {
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
}

//처음에 인덱스가 같을 때를 제외하고 모든 공간을 무한대로 처리(987654321)
void setting() {
    for(int i = 1; i < MAX; i++) {
        for(int j = 1; j < MAX; j++) {
            if(i != j) {
                d[i][j] = 987654321;
            }
        }
    }
}

int main() {
    setting();
    
    cin >> n >> m >> r;
    for(int i = 1 ; i <= n; i++) { //마을의 아이템을 초기화
        cin >> item[i];
    }
    
    //양 방향으로 마을이 연결
    for(int i = 0; i < r; i++) {
        cin >> a >> b >> l;
        d[a][b] = l;
        d[b][a] = l;
    }
    
    floydWashall();
    
    for(int i = 1; i <= n; i++) {
        int cnt = item[i]; //시작하는 마을을 비용으로 넣는다.
        for(int j = 1; j <= n; j++) {
            if(i == j) { //같은 마을이면
                continue; //무시
            }
            if(d[i][j] <= m) { //다른 마을이고 비용이 m이하이면
               cnt = cnt + item[j]; //현재 마을에서 더한다.
            }
        }
        ans = max(ans, cnt); //더 많이 먹은 결과를 얻는다.
    }
    
    cout << ans;
    
    return 0;
}