HERSTORY

[C++ 알고리즘] 백준 1238번 : 파티

  • 2021년 02월 15일


파티

풀이과정

다익스트라 알고리즘을 이용해 문제를 해결하였다. 이 문제를 풀기 전에 같은 다익스트라 문제인 1753번, 1916번 문제를 먼저 풀어보는게 좋다.

다익스트라 알고리즘
간선의 가중치가 모두 양수일 때 사용하는 알고리즘이다. 항상 최소 비용을 비교하여 갱신한다. 최단 거리가 정해진 노드는 더 이상 방문하지 않는다.
  1. 간선(도로)의 정보를 저장한다.
  2. x 도시에서 y 도시로의 최단 거리를 저장할 이차원 배열 dist를 생성하고 기본값을 INT의 최대값으로 설정한다. dist[x][y] 는 x에서 y로의 최단 거리이다.
  3. 각 도시에 대해 다익스트라를 수행한다. 우선순위 큐(최소힙)를 이용해 가중치(시간)가 가장 작은 것을 고른다.
  4. x도시에 사는 학생이 k도시를 왕복하는 최단거리는 dist[x][k] + dist[k][x]이다.
  5. dist[x][k] + dist[k][x] 중 최대값을 찾는다.


코드

#include <iostream>
#include <limits.h>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

struct edge {
    int end;
    int weight;
    edge(int a, int b) {
        end = a;
        weight = b;
    }
    bool operator<(const edge& e)const {
        return weight > e.weight;
    }
};

int main()
{
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);

    int n, m, x;
    cin >> n >> m >> x;

    int s, e, w;
    vector<edge> graph[1001];
    for (int i = 0; i < m; i++) {
        cin >> s >> e >> w;
        graph[s].push_back(edge(e, w));
    }

    vector<vector<int> > dist(n + 1, vector<int>(n + 1, INT_MAX));
    for (int i = 1; i <= n; i++) {
        priority_queue<edge> pQ;
        pQ.push(edge(i, 0));
        dist[i][i] = 0;

        while (!pQ.empty()) {
            e = pQ.top().end;
            w = pQ.top().weight;
            pQ.pop();

            //최단 거리가 정해진 곳은 방문하지 않음
            if (w > dist[i][e]) continue;

            for (auto it = graph[e].begin(); it != graph[e].end(); it++) {
                int a, b;
                a = (*it).end;
                b = (*it).weight;

                if (dist[i][a] > dist[i][e] + b) {
                    dist[i][a] = dist[i][e] + b;
                    pQ.push(edge(a,dist[i][a]));
                }
            }
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i++) {
        res = max(res, dist[x][i] + dist[i][x]);
    }
    cout << res;

    return 0;
}



검색