[백준 14938] 서강그라운드 (C++) - 50

문제

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

14938번: 서강그라운드

생각

다익스트라 알고리즘을 활용해!

코드

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
const int INF = 987654321;

int n, m, r;
int item[101];
vector <pair<int, int>> map[101];
int dist[101];
bool vst[101];
int ans = -1;;
int sum, l;

void dijkstra (int start) { 
    for(int i = 0; i <= n; i++) dist[i] = INF;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[start] = 0;
    pq.push({ 0, start });

    while (!pq.empty()) {
        int cost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        
        if(!vst[cur]){
            vst[cur] = true;
            for (int i = 0; i < map[cur].size(); i++) {
                int neighbor = map[cur][i].first;
                int neighCost = map[cur][i].second;

                int neighborDistance = cost + neighCost;
                if (dist[neighbor] > neighborDistance){
                    dist[neighbor] = neighborDistance;
                    pq.push({ neighborDistance, neighbor });
                }
            }
        }
    }
}

int main() {
    cin >> n >> m >> r;
    for(int i = 1; i <= n; i++) cin >> item[i];
    for(int i = 1; i <= r; i++) {
        int a, b, l;
        cin >> a >> b >> l;
        map[a].push_back({b, l});
        map[b].push_back({a, l});
    }

    for(int i = 1; i <= n; i++) {
        memset(vst, false, sizeof(vst));
        sum = 0;
        queue<pair<int, int>> q;
        dijkstra(i);
        for(int j = 1; j <= n; j++){
            if(dist[j] <= m) sum += item[j];
        }
        ans = max(ans, sum);
    }

    cout << ans;
}