baekjoon 14938:서강그라운드

baekjoon 14938 서강그라운드

14938번 서강그라운드

접근

dijkstra쓰면 바로 풀릴 문제이다. dijkstra는 queue에 .d값들 다 넣어두고 최솟값들 뽑아내면서 그 점의 adj을 relax시키면 된다.
원래는 S라는 집합에 queue에서 뽑은 점을 하나씩 넣고 없는 점 중에 min d를 찾는 것인데 이를 구현할 때
distance라는 배열을 만들어 놓고 distance[] < queue.d로 이미 탐색 한 점인지 판단할 수 있다.

코드

#include <iostream>
#include <vector>
#include <array>
#include <queue>
#define MAX 1e9
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n, m, r; cin >> n >> m >> r;
  vector<int> item(n, 0);
  for(int i = 0; i < n; i++){
    cin >> item[i];
  }
  vector<vector<array<int, 2>>> adj(n);
  for(int i = 0; i < r; i++){
    int a, b, c; cin >> a >> b >> c;
    adj[a-1].push_back({b-1, c});
    adj[b-1].push_back({a-1, c});
  }
  priority_queue<int> pqAns;
  for(int i = 0; i < n; i++){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<int> distance(n, MAX);
    distance[i] = 0;
    pq.push({0, i});
    while(!pq.empty()){
      pair<int, int> curr = pq.top();
      pq.pop();
      if(distance[curr.second] < curr.first){
        continue;
      }
      //포함
      for(auto& j : adj[curr.second]){
        if(distance[j[0]] > distance[curr.second] + j[1]){
          distance[j[0]] = distance[curr.second] + j[1];
          pq.push({distance[j[0]], j[0]});
        }
      }
    }
    int tempAns = 0;
    for(int j = 0; j < n; j++){
      if(distance[j] <= m){
        tempAns += item[j];
      }
    }
    pqAns.push(tempAns);
  }
  cout << pqAns.top();
  
  
  return 0;
}

배운 점

dijkstra 구현 연습. dijkstra는 가중치 방향그래프인데, 음의 가중치 안되고 one source 최단거리이다.