[백준] 14938번 서강그라운드(c++)

문제 및 입출력

문제 접근

모든 노드들 기준으로 다익스트라를 돌려주었다.
그리고 다익스트라가 한번 끝날 때마다, 예은이가 있는 위치에서 해당 노드들과의 거리를 확인해서 예은이가 탐색할 수 있는 거리일 때만, 아이템을 더해주었다.
그리고 최대값을 구해주었다.

코드 구현(c++)

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

#define INF 1e9
#define MAX 101

using namespace std;

vector<pair<int,int> > v[MAX];
int n,m,r;

int items[MAX];
int dist[MAX];

int res = -1;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;

void init(){
    for(int i = 1 ; i <= n ; i++){
        dist[i] = INF;
    }
}
void dijkstra(int x){
    init();
    dist[x] = 0;
    pq.push(make_pair(0,x));
    while(!pq.empty()){
        //지금꺼와 지금 연결되어 있는 노드들에 저장되어 있는 길이 체크 후 더 작은 거 넣기.
        int d = pq.top().first; int cur = pq.top().second;
        pq.pop();
        for(int i = 0 ; i < v[cur].size() ; i++){
            int nD = v[cur][i].second;
            int next = v[cur][i].first;
            if(dist[next] > nD + d){
                dist[next] = nD + d;
                pq.push(make_pair(nD + d, next));
            }
        }
    }
    int curItems = 0;
    for(int i = 1 ; i <= n ; i++){
        if(dist[i] <= m) curItems += items[i];
    }
    res = max(res, curItems);
}

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

    cin >> n >> m >> r;
    for(int i = 1 ; i <= n ; i++){
        cin >> items[i];
    }
    int n1, n2, d;
    for(int i = 0 ; i < r ; i++){
        cin >> n1 >> n2 >> d;
        v[n1].push_back(make_pair(n2,d));
        v[n2].push_back(make_pair(n1,d));
    }
    for(int i = 1 ; i <= n ; i++){
        dijkstra(i);
    }
    cout << res << "\n";

}