[백준 14938번] [Dijkstra] 서강그라운드

Approach

정해진 출발점을 기준으로 최단거리가 m보다 작으면 방문할 수 있는 정점이라는 아이디어를 파악했으면

모든 정점을 출발점으로 설정하고, 다익스트라를 통해 최단거리가 m보다 더 작은 모든 정점에 속한 아이템의 수를 다 더해준 뒤 그 중 최댓값을 출력해주면 된다.

Code

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int move_x[4] = {-1, 1, 0, 0};
int move_y[4] = {0, 0, -1, 1};
const int INF = 1000000000;

//ElogV * V
int main() {
    fastio;
    int n, m, r;
    cin >> n >> m >> r;

    vector<pii> edge[n];
    vector<int> item(n);

    for(int i = 0; i < n; i++){
        cin >> item[i];
    }

    for(int i = 0; i < r; i++){
        int a, b, c;
        cin >> a >> b >> c;
        edge[a - 1].push_back({b - 1, c});
        edge[b - 1].push_back({a - 1, c});
    }

    int max_item_num = 0;
    for(int i = 0; i < n; i++){
        int s = i;
        vector<int> dist(n, INF);
        dist[s] = 0;
        priority_queue<pii, vector<pii>, greater<pii> > pq;
        pq.push({0, s});
        while(!pq.empty()){
            int cur_cost = pq.top().first, cur = pq.top().second;
            pq.pop();
            if(dist[cur] < cur_cost) continue;
            for(auto &p : edge[cur]){
                int to = p.first, cost = p.second;
                if(cur_cost + cost < dist[to]){
                    dist[to] = cur_cost + cost;
                    pq.push({dist[to], to});
                }
            }
        }

        int total_item_num = 0;

        for(int j = 0; j < n; j++){
            if(dist[j] <= m){
                total_item_num += item[j];
            }
        }
        max_item_num = max(max_item_num, total_item_num);
    }

    cout << max_item_num << "\n";
    return 0;  
}