[ 백준 1238 ] 파티 (C++)

백준의 파티(1238) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

N명의 학생들이, X번 마을로 갔다가, 다시 자신들의 원래의 마을로 돌아오는데 가장 오래 걸리는 학생의 소요시간을 출력해야

하는 문제이다.

그래프에서 단방향 도로들의 가중치가 양의 정수로만 이루어져 있으므로 본인은 다익스트라 알고리즘을 이용해서 접근해보았다. 다익스트라 알고리즘을 총 2번을 진행해주었는데, 첫 번째 다익스트라의 경우는 모든 학생들이 'X번 마을로 가는데 걸리는

최단 소요시간' 을 찾기위함이고, 두 번째 다익스트라의 경우는 'X번 마을에서 다시 자신들의 원래 마을로 가는데 걸리는

최단 소요시간' 을 찾기 위해서 진행해 주었다.

도로가 '단방향' 이기 때문에, A번 마을에 X번 마을로 가는데 'T'만큼의 시간이 걸렸다고 하더라도, X번 마을에서 A번 마을로 다시 돌아가는데 'T'만큼의 시간이 걸린다는 보장이 없기 때문에 위와같이 다익스트라를 총 2번 진행해 주었다.

그 과정에서, 각 학생들의 걸리는 시간들을 저장할 배열을 하나 만들어서, 시간을 저장해 주면서 진행해 주었다.

최종적으로는, 시간을 저장해준 배열에서 가장 큰 값을 찾아서 출력시켜주었다.

다익스트라를 구현하는 것이 핵심인 문제라고 생각한다. 아직 다익스트라 알고리즘에 대해서 잘 모른다면 아래의 글을

읽고 오도록 하자.

[ 다익스트라 알고리즘 알아보기(Click) ]

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
 
#define endl "\n"
#define MAX 1010
#define INF 987654321
using namespace std;
 
int N, M, X, Answer;
int Dist[MAX], Res[MAX];
vector<pair<int,int>> V[MAX];
 
void Input()
{
    cin >> N >> M >> X;
    for (int i = 0; i < M; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        V[a].push_back(make_pair(b, c));
    }
}
 
void Dijkstra(int Start)
{
    priority_queue<pair<int, int>> PQ;
    Dist[Start] = 0;
    PQ.push(make_pair(0, Start));
 
    while (PQ.empty() == 0)
    {
        int Cost = -PQ.top().first;
        int Cur = PQ.top().second;
        PQ.pop();
 
        for (int i = 0; i < V[Cur].size(); i++)
        {
            int Next = V[Cur][i].first;
            int nCost = V[Cur][i].second;
 
            if (Dist[Next] > Cost + nCost)
            {
                Dist[Next] = Cost + nCost;
                PQ.push(make_pair(-Dist[Next], Next));
            }
        }
    }
 
}
 
void Solution()
{
    for(int i = 1; i <= N; i++)
    { 
        for (int j = 1; j <= N; j++) Dist[j] = INF;
        Dijkstra(i);
        Res[i] = Dist[X];        
    }
    for (int j = 1; j <= N; j++) Dist[j] = INF;
    Dijkstra(X);
    for (int i = 1; i <= N; i++) Res[i] = Res[i] + Dist[i];
    sort(Res + 1, Res + N + 1);
    Answer = Res[N];
}
 
void Solve()
{
    Input();
    Solution();
    cout << Answer << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}