7주차(최단경로) - [C++]백준1238 파티

01 May 2022 in Study on Algorithm

백준1238 파티 링크

문제

예제 입력

---

코드

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

int n, m, x;
vector<pair<int, int>> Graph[1001];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int Dist[1001];
int arr[1001];

void dijkstra(int start) {
    fill(Dist, Dist + n + 1, INF);
    Dist[start] = 0;
    pq.push({ Dist[start],start });

    while (!pq.empty()) {
        auto cur = pq.top();
        pq.pop();
        if (Dist[cur.second] < cur.first) continue;
        for (auto nxt : Graph[cur.second]) {
            if (Dist[nxt.first] > Dist[cur.second] + nxt.second) {
                Dist[nxt.first] = Dist[cur.second] + nxt.second;
                pq.push({ Dist[nxt.first], nxt.first });
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); //cin 실행속도 향상

    cin >> n >> m >> x;
    for (int i = 0; i < m; i++) {
        int from, to, dist;
        cin >> from >> to >> dist;
        Graph[from].push_back({ to, dist });
    }

    // 각 지점에서 X까지 가는 길 
    for (int i = 1; i <= n; i++) {
        if (i == x) continue;
        dijkstra(i);
        arr[i] = Dist[x];
    }
    // X에서 지점까지 가는 길
    dijkstra(x);

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (ans < Dist[i] + arr[i])
            ans = Dist[i] + arr[i];
    }
    cout << ans << "\n";
}

설명

이 문제는 각 마을에 한 명의 학생이 살고 그중 한 마을에서 파티가 열려서 모두가 파티가 열린 마을에 갔다가 다시 본인 마을로 가야합니다. 이때 최단 경로로 갔다가 오는데 가장 많이 소비되는 시간을 구하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 vector와 Queue를 사용하여 구현했습니다. 방향 그래프와 시작점을 입력 받아 최단 경로를 찾기 위해서 다익스트라 알고리즘을 사용하는데 특정 시작점으로부터 종료점이나 다른 정점과의 최단 경로를 찾습니다. 모든 마을에서 파티가 열린 마을까지 가는 최단 경로를 각각 구하여 arr에 따로 저장하고 돌아갈때는 파티가 열린 마을에서 다른 마을의 최단 경로가 Dist에 저장됩니다. 최소 힙을 사용하여 각 정점으로 가는 경로에 대한 값을 넣어주고 이미 있다면 비교하여 최단 경로로 갱신 해줍니다. 마지막으로 두 경로를 합쳐서 가장 많은 시간을 소비한 시간을 출력합니다.

-pair<자료형, 자료형> 변수명; : 하나의 변수에 2가지 값을 저장함

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

<queue>
-priority_queue<자료형, 자료형태, 비교함수> 변수명; : 우선순위 큐(힙) 자료구조 사용
<비교함수>
-greater<자료형> : 내림차순 정렬
-less<자료형> : 오름차순 정렬

---

결과