백준 14938번: 서강그라운드 (C++)

문제링크

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

풀이방법

해당 문제는 플로이드 알고리즘을 이용하여 해결할 수 있다. 풀이 방법은 다음과 같다.

• 우선 플로이드 알고리즘을 구현하여 인접 배열을 통해서 특정 노드와 특정 노드 사이의 최단 거리를 모두 구한다.
• 또한 unordered_map을 이용하여 특정 노드의 아이템 개수를 저장해둔다.
• 마지막으로 시작지점 1~n 까지 각 노드로부터 수색 범위(m) 이하에 존재하는 아이템 개수를 모두 더해서 vector 에 저장해둔다. result에는 각 시작 지점 별로 수색 범위(m) 이하에 존재하는 아이템 개수를 더한 값이 들어있다.
• 마지막으로 result에 들어있는 값 중 가장 큰 값을 출력하면 정답이 된다.

코드

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;

const int INF = 0x3f3f3f3f;
int d[105][105];
int n, m, r;
unordered_map<int, int> um;
vector<int> result;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> r;
    for (int i = 1; i <= n; i++)
        fill(d[i], d[i] + 1 + n, INF);

    for (int i = 1; i <= n; i++)
    {
        int t;
        cin >> t;
        um[i] = t;
    }

    while (r--) {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c);
        d[b][a] = min(d[b][a], c);
    }
    for (int i = 1; i <= n; i++) d[i][i] = 0;

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);


    for (int i = 1; i <= n; i++)
    {
        int ans = um[i];
        for (int j = 1; j <= n; j++)
        {
            if (i == j) continue;
            if (d[i][j] <= m) ans += um[j];
        }
        result.push_back(ans);
    }
    cout << *max_element(result.begin(), result.end());
}