[백준] 1238번 파티

[적용한 알고리즘]

다익스트라

 

[아이디어]

1~N까지 다익스트라를 실행해 X까지 가는 최소비용을 각각 구해준뒤 각 마을의 time 배열에 더해준다.

다만 X 일때는 각자의 마을로 돌아가는 것이므로, 이때는 X를 제외한 모두에게 최소비용을 더해준다.

 

[생각의 흐름 / 절차] 

내용

 

[교훈]

익숙해지는 중.

 

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> P;
const int MAX_N = 1001;
const int INF = 1000000000;
int N, M, X;

int main(){
    scanf("%d %d %d", &N, &M, &X);
    vector<P> adj[MAX_N];

    for (int i = 0; i < M; i++){
        int from, to, cost;
        scanf("%d %d %d", &from, &to, &cost);
        adj[from].push_back(P(to, cost));
    }

    int time[MAX_N] = { 0 };

    for (int i = 1; i <= N; i++){ //1~N 까지 다익스트라
        int dist[MAX_N]; fill(dist, dist + N + 1, INF);
        bool visited[MAX_N] = { 0 };
        priority_queue<P, vector<P>, greater<P>> PQ;

        dist[i] = 0;
        PQ.push(P(0, i));

        while (!PQ.empty()){
            int cur;

            do {
                cur = PQ.top().second; //현재 노드
                PQ.pop();
            } while (!PQ.empty() && visited[cur]);

            // 현재 X 노드에서 다익스트라를 쓰지 않고, 방문한 노드가 X라면 종료.
            // 이미 X에서 경로 cost 의 최솟값은 알 것이기 떄문에
            if (i != X && cur == X) break;
            if (visited[cur]) break;
            visited[cur] = true;

            for (auto &p : adj[cur]){
                int nxt_node = p.first;
                int nxt_cost = p.second;

                if (dist[nxt_node] > dist[cur] + nxt_cost){
                    dist[nxt_node] = dist[cur] + nxt_cost;
                    PQ.push(P(dist[nxt_node], nxt_node));
                }
            }
        }
        // X에서 시작한 다익스트라의 경우 X에서 각자 집으로 돌아가는 거기 때문에 경로 최솟값들을 다 더해줌.
        if (i == X){
            for (int k = 1; k <= N; k++){
                if (k == X) continue;
                time[k] += dist[k];
            }
        }
        // X에서 시작한게 아니라면, X까지의 dist 값을 알아내서 더해주면 됨.
        else {
            time[i] += dist[X];
        }
    }

    int ans = -1;
    for (int i = 1; i <= N; i++){
        ans = max(time[i], ans);
    }

    printf("%d\n", ans);

    return 0;
}