[백준] 파티_1238

다익스트라 알고리즘을 이용하여 푸는 문제. 다익스트라 알고리즘은 1학년 과목에서 배웠던 거지만... 지금 와서 다시 보니 또 새롭다ㅎㅎ 구현을 해보는건 처음이다. 

 

** priority queue

priority_queue<graph,vector<graph>,compare> pq; 

이렇게 굳이 struct를 따로 만들고 compare 함수를 정의할 필요없이, 

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> 

이렇게 하는 방법도 있다. (functional 헤더 붙이기)  

priority_queue<pair<int, int>> 이렇게만 하면 기본적으로 first를 기준으로, 가장 큰 원소부터 뽑는다.

compare 함수를 따로 정의해주거나, -를 붙여 부호를 반대로 한 뒤 push하면 가장 작은 값부터 뽑아낼 수 있다.

 

하지만 이번에는 코드의 가독성을 위해서 구조체를 따로 정의하여 문제를 풀어보았다. 

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
const int INF = 0x7FFFFFFF;
int N, M, X;
 
struct graph {
    int vertex;
    int cost;
};
struct compare {
    bool operator()(graph g1, graph g2) {
        return g1.cost > g2.cost;
    }
};
 
vector<graph> vill[1001];
priority_queue<graph,vector<graph>,compare> pq;
 
int Dijkstra(int start, int fin) {
    vector<int> result(N + 1, INF);
    result[start] = 0;
    pq.push(graph{ start, 0 });
    while (!pq.empty()) {
        int v = pq.top().vertex;
        int cost = pq.top().cost;
        pq.pop();
        if (result[v] < cost) continue;
        for (int i = 0; i < vill[v].size(); i++) {
            int adjV = vill[v][i].vertex;
            int adjCost = vill[v][i].cost + result[v];
            if (result[adjV] > adjCost) {
                result[adjV] = adjCost;
                pq.push(graph{ adjV, adjCost });
            }
        }
    }
    return result[fin];
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N >> M >> X;
    int u, v, w;
    for (int i = 0; i < M; i++) {
        cin >> u >> v >> w;
        vill[u].push_back(graph{ v,w });
    }
    
    int max = 0;
    for (int i = 1; i <= N; i++) {
        int res = Dijkstra(X, i) + Dijkstra(i, X);
        if (max < res) max = res;
    }
    cout << max;
    return 0;
}