(C++) 백준 14938 서강그라운드 (Dijkstra)

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

한 정점에서 다른 정점으로 가는 최단 경로를 계산해야 하는 다익스트라 문제.
일반적인 DFS/BFS 문제처럼 방문여부를 통해 정점 방문여부를 따지는것이 아니라, 기준 정점과의 거리가 최소일 때 정점 방문을 할지 결정한다.

문제 조건에 따르면 한 정점에서 방문할 수 있는 거리에 있는 모든 노드들을 찾아 이 노드들이 가지고 있는 아이템을 계산해야 한다. 따라서 1~n번까지 for문을 돌며 모든 노드들에 다익스트라를 적용했다.

• 다익스트라

    for(int i=1; i<=n; i++){
    	// 현재 노드 i와 다른 노드 사이의 거리 초기화 
        // 아직 방문하지 않았거나 방문할 수 없는 노드는 최대값(INF) 이다.
        for(int j=1; j<=n; j++) D[j]=INF;
        D[i]=0; // 자기 자신과의 거리는 0

        priority_queue<pair<int, int>> pq;
        pq.push({i,0});

        while(!pq.empty()){

            int node = pq.top().first;
            int dist = -pq.top().second; 
            pq.pop();

            for(int k=0; k<(int) v[node].size(); k++){
                int next = v[node][k].first;
                int nextD = dist + v[node][k].second;

                // 노드 i와 현재 노드(next)의 거리가 
                // 이전에 계산된(D[next]) 값보다 작으면 갱신하고 다시 큐에 넣음
                if(D[next]>nextD){
                    D[next]=nextD;
                    // 거리가 작을수록 우선순위가 크므로, 음수로 입력
                    pq.push({next, -nextD});
                }
            }

        }

• 전체코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;



const int INF = 1000000000;
int n,m,r;
int items[105];
int D[105];
int a,b,l;
int ans;
vector<vector<pair<int, int>>> v(105);


int main(){
    cin>>n>>m>>r;
    for(int i=1; i<=n; i++) cin>>items[i];

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


    for(int i=1; i<=n; i++){
 
        for(int j=1; j<=n; j++) D[j]=INF;
        D[i]=0;


        priority_queue<pair<int, int>> pq;
        pq.push({i,0});


        while(!pq.empty()){

            int node = pq.top().first;
            int dist = -pq.top().second;
            pq.pop();

            for(int k=0; k<(int) v[node].size(); k++){
                int next = v[node][k].first;
                int nextD = dist + v[node][k].second;

                if(D[next]>nextD){
                    D[next]=nextD;
                    pq.push({next, -nextD});
                }
            }

        }

        int tmp=0;
        for(int k=1; k<=n; k++) {
            if(D[k]<=m) tmp+=items[k];
        }
        ans = max(tmp, ans);
    }


    cout<<ans;

}