[BOJ 1238] 파티 (C++)

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

1238번: 파티

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

class Node{
    public:
        int id;
        int cost;
        Node(int id, int cost){
            this->id=id;
            this->cost=cost;
        }
};

struct compare{
    bool operator()(const Node& a, const Node& b){
        return a.cost>b.cost;
    }
};

int main(){
    int N, M, X;
    int s, e, T;
    cin>>N>>M>>X;
    int dist_jip[N+1];  //각자 집이 출발지
    int time[N+1];
    memset(time, 0, sizeof(int)*(N+1));
    vector<vector<Node> > adjList(N+1);
    for (int i=0; i<M; i++){
        cin>>s>>e>>T;
        adjList[s].push_back(Node(e,T));
    }
    for (int i=1; i<=N; i++){
        for (int j=1; j<=N; j++){
            dist_jip[j]=INF;
        }
        priority_queue<Node, vector<Node>, compare> pq;
        pq.push(Node(i,0));
        dist_jip[i]=0;      //i에서 도착지까지 걸리는 시간
        while (!pq.empty()){
            Node now=pq.top();
            pq.pop();
            if (now.id==X && i!=X){
                time[i]+=dist_jip[X];
                break;
            }
            if (now.cost > dist_jip[now.id]){
                continue;
            }
            int len=adjList[now.id].size();
            for (int j=0; j<len; j++){
                Node next=adjList[now.id][j];
                if (dist_jip[next.id] > now.cost+next.cost){
                    dist_jip[next.id]=now.cost+next.cost;
                    pq.push(Node(next.id, dist_jip[next.id]));
                }
            }
        }
        if (i==X){      //돌아오는데 걸리는 시간
            for (int j=1; j<=N; j++){
                time[j]+=dist_jip[j];
            }
        }
    }
    int max=0;
    for (int i=1; i<=N; i++){
        if (max < time[i]){
            max=time[i];
        }
    }
    cout<<max<<"\n";
    return 0;
}

다익스트라 여러번 돌려서 해결하는 문제.

 

각 i에서 ---> X까지 dijkstra를 N번 돌려주면(X의 경우에는 X에서 나머지 도착지까지) 된다.

time에 구해진 최단 거리를 저장한다.

dijkstra가 출발지가 고정되어 있을 때 사용된다는 점을 인지하기.