[백준 14938] 서강그라운드

 

 그래프 이론 중에서 최단 거리 문제다. 요새 계속 어려운 문제만 풀었더니, 처음에 입력 값의 크기가 너무 작아서 내가 문제에서 뭔가 놓쳤는지 의심부터 했다.

 각 지역마다 다른 지역들까지의 최단 거리를 구해서, 수색범위 보다 작은 비용으로 도달할 수 있는 구역의 아이템 가치를 더해서 얻을 수 있는 아이템 가치 총합을 구한다. 그리고 어떤 지역에서 시작할 때 얻을 수 있는 아이템 가치 총합이 가장 큰 지 판별하면 끝이다.

 

 최단 거리를 구하는 알고리즘들은 너무 잘 알려져 있고, 대표적으로 다익스트라 알고리즘, 플로이드-워셜 알고리즘, 벨만-포드 알고리즘이 있다. 노드와 간선의 수가 둘 다 최대 100밖에 되지 않고, 간선이 음의 가중치를 가지는 경우도 없기 때문에 사실 뭘 선택해도 문제없이 해결된다. 

 나는 음의 가중치를 가지는 간선이 없으므로, 다익스트라 알고리즘을 택했다. 또 노드와 간선이 최대치로 들어왔을 때 미세하게 가장 빠르긴 할 것이다. 

 

 구현은 특별할 것 없이, 우선순위 큐를 이용해 다익스트라 알고리즘을 구현하고 모든 노드에 대해 한번씩 실행해 보며 최적해를 찾았다. 물론 이미 한 번 판별된 노드끼리의 거리는 다시 탐색할 필요가 없으므로, 글로벌한 메모이제이션을 이용해서 좀 더 최적화할 순 있었겠지만 인풋이 작아서 오히려 그 비용이 더 클 것 같아서 굳이 하지는 않았다. 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 987654321

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, r;
    cin >> n >> m >> r;

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

    vector<vector<pair<int, int> > > adjList(n+1);
    int a, b, l;

    for(int i=0; i<r; i++) {
        cin >> a >> b >> l;
        adjList[a].push_back({b, l});
        adjList[b].push_back({a, l});
    }

    int maxItemValueSum = 0;
    for(int i=1; i<=n; i++) {
        vector<int> dist(n+1, INF);
        priority_queue<pair<int, int> > pq; //{-cost, target}
        pq.push({0, i});

        int getItemValueSum = 0;
        while(!pq.empty()) {
            int curCost = -pq.top().first;
            int curNode = pq.top().second;
            pq.pop();

            if(curCost>=dist[curNode]) continue;
            if(curCost<=m) getItemValueSum += items[curNode];
            dist[curNode] = curCost;

            for(auto edge: adjList[curNode]) {
                if(dist[edge.first]>=curCost+edge.second) {
                    pq.push({-(curCost+edge.second), edge.first});
                }
            }
        }
        maxItemValueSum = max(maxItemValueSum, getItemValueSum);
    }

    cout << maxItemValueSum;
}