[Algorithm] 백준 14938 - 서강그라운드, C++, 다익스트라

14938번: 서강그라운드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;

int n, m, r;   // 지역, 수색범위, 길의 수
int item_in_area[101];
int cost_from_start[101];
vector<pair<int, int>> edges[101];

void Yeeun_Search(int start_pos){
    // init array
    for(int i = 1; i <= n; i++)
        cost_from_start[i] = INT32_MAX;
    

    queue<int> q;
    q.push(start_pos);
    cost_from_start[start_pos] = 0;

    // search
    while (!q.empty()){
        int cur = q.front();
        q.pop();

        for(int i = 0; i < edges[cur].size(); i++){
            int next_pos = edges[cur][i].first;
            int next_cost = edges[cur][i].second;

            if(cost_from_start[next_pos] > cost_from_start[cur] + next_cost){
                cost_from_start[next_pos] = cost_from_start[cur] + next_cost;
                q.push(next_pos);
            }
        }
    }
    
}


int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // input
    cin >> n >> m >> r;

    for(int i = 1; i <= n; i++)
        cin >> item_in_area[i];
    
    for(int i = 0; i < r; i++){
        int a, b, l;
        cin >> a >> b >> l;

        edges[a].push_back({b, l});
        edges[b].push_back({a, l});
    }


    // solution
    int max_items = 0;

    for(int i = 1; i <= n; i++){
        Yeeun_Search(i);

        int items = 0;
        for(int j = 1; j <= n; j++){
            if(cost_from_start[j] <= m)
                items += item_in_area[j];
        }
        max_items = max(max_items, items);
    }


    // print
    cout << max_items << endl;

    return 0;
}

---

 다익스트라 함수를 보통 형태로 만든 뒤 for문에서 호출한 뒤 cost_from_start에서 비용이 되는 곳만 계산하는 형식입니다. 다익스트라 함수 내에서 계산하는 방식은 어떨까 했는데 연결된 지점이 많아지면 비교문이 늘어날 것 같아서 이 방식으로 선택했습니다.