[백준/BOJ] acmicpc 14938 서강그라운드 C++ (다익스트라)

문제

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

 

풀이

1. 하나의 정점을 출발지로 두고 다익스트라 알고리즘으로 모든 정점까지의 최단 거리 값을 구한다.

(cost가 모두 양수이고 각 정점까지의 최단거리를 구하면 되므로 다익스트라 사용)

2. 최단거리가 예은이의 수색 범위 이하에 있는 모든 정점의 item값의 합을 구한다.

3. 출발지를 1~n까지 모두 설정하여 2를 구하고 최대값을 출력한다.

 

코드

#include<iostream>
#include <vector>
#include <queue>
#define INF 1e9
using namespace std;

int n, range, r, answer = 0;
vector<pair<int, int>> graph[101];
int item[101];

// 출발점이 departure일 때 조건을 만족하는 item값의 합을 출력
int dijkstra(int departure){
    int dist[101];
    fill_n(dist, n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push({0, departure});
    dist[departure] = 0;
    while (!pq.empty()){
        auto [cost, curr] = pq.top();
        pq.pop();

        for(long unsigned int i = 0; i< graph[curr].size(); i++){
            auto [next, nextCost] = graph[curr][i];
            if(dist[next] <= cost + nextCost) continue;

            dist[next] = cost + nextCost;
            pq.push({dist[next], next});
        }
    }

    int sum = 0;
    for(int i = 1;i <= n; i++){
        if(dist[i] > range ) continue;
        sum += item[i];
    }
    return sum;
}

int main(){
    cin >> n >> range >> r;
    for(int i = 1; i<=n; i++){
        cin >> item[i];
    }
    for(int i = 0; i < r ; i++){
        int from, to, cost;
        cin >> from >> to >> cost;
        graph[from].push_back({to, cost});
        graph[to].push_back({from, cost});
    }

    for(int i = 1; i<= n; i++){
        answer = max(answer, dijkstra(i));
    }

    cout << answer <<"\n";

}

 

 

핵심

dijkstra()함수의 인자로 출발점을 받아 각 출발지에 대해서 sum값을 계산하여 return하도록 했다.

뒤에 sum 계산하는 부분을 다른 함수로 뺄까 하였으나 ... 그냥 다익스트라 내부에서 하도록 함 ...

 

main 함수에서 dijkstra 호출하는 부분에 max()함수로 answer값을 갱신해서 그때그때 최고치를 저장하고

sort할 필요 없도록 했다.

 

 

 

풀이 흔적

처음에 다익스트라 내부 for문 안에서 dist값을 갱신해 줄 때 예은이의 수색범위를 넘어가면 그냥 continue하는 식으로 짜려했었다.

이땐 문제를 잘못이해해서 출발지점이 주어지는 줄 알았었는데, 다시 보니 모든 정점을 시작점으로 다 다익스타를 돌아야하는거라서

그냥 안썼다. 

근데 글 포스팅 하다가 이 줄을 추가해주면 달라질까? 해서 한번 다시 제출해봤다.

for(long unsigned int i = 0; i< graph[curr].size(); i++){
    auto [next, nextCost] = graph[curr][i];
    if(dist[next] <= cost + nextCost) continue;
    
    if(cost + nextCost > range) continue; //추가해준 부분
    dist[next] = cost + nextCost;
    pq.push({dist[next], next});
}

다른 부분은 다 똑같고, 다음 갱신값이 예은이의 수색범위 넘어가면 continue 하는 코드만 추가해줬다.

 

 

근데 워낙 테스트케이스 범위가 작아서 그런지 시간도 0ms로 찍혀서 차이가 없었음,,,

그래도 테케 범위가 넓었으면 수정한 코드로 하는게 나을것 같긴하다.