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

문제 출처 : https://www.acmicpc.net/problem/1238

1238번: 파티

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int dis[1001];
vector<vector<pair<int, int>>> v(1001);
 
void dijk(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({ 0, start });
    dis[start] = 0;
    int distance, now, cost;
 
    while (!pq.empty()) {
        distance = pq.top().first;
        now = pq.top().second;
        pq.pop();
 
        if (dis[now] < distance) continue;
 
        for (int i = 0; i < v[now].size(); i++) {
            cost = distance + v[now][i].second;
            if (cost < dis[v[now][i].first]) {
                dis[v[now][i].first] = cost;
                pq.push({ cost, v[now][i].first });
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m, a, b, c, s, temp, maxtime = 0;
    cin >> n >> m;
    cin >> s;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        v[a].push_back(make_pair(b, c));
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dis[j] = 1000000000;
        }
        dijk(s);
        temp = dis[i];
        for (int j = 0; j <= n; j++) {
            dis[j] = 1000000000;
        }
        dijk(i);
        maxtime = max(maxtime, temp + dis[s]);
    }
    cout << maxtime;
    return 0;
}

 

알고리즘

- 그래프 이론

- 데이크스트라

 

모여야 하는 마을 s를 입력받는다.

도로의 시작점, 끝점, 시간을 입력 받고 v[시작점]에 pair(끝점, 시간)을 넣어준다.

 

모든 마을에 대해서 왕복 시간을 구해준다.

시간배열을 무한값(10억)으로 초기화 한 후 모여야 하는 마을 s로 dijk함수를 돌려준다.

s에서 i까지의 시간을 temp에 저장해 둔 후 시간배열을 초기화 한다.

i에 대해 dijk함수를 돌린 후 i에서 s까지의 시간을 구해준다.

s에서 i까지의 시간과 i에서 s까지의 시간의 합과 현재 들고있는 maxtime(답)을 비교하여 큰 값을 저장한다.

 

maxtime을 출력한다.

 

dijk 함수
오름차순 우선순위큐(pair)를 선언한다. (시간 오름차순으로 정렬)
start에서 start까지의 시간은 0이므로 (0, start)를 넣는다.
dis[start]도 0으로 업데이트 한다.

큐가 빌 때까지 반복문을 돈다.

distance에는 큐 top의 첫번째 값을, now에는 큐 top의 두번째 값을 넣고 pop 한다.

dis[now] < distance 라면 이미 체크한 노드이므로 다음 노드를 확인한다.

now와 연결된 노드를 모두 확인한다.
start에서 해당 노드에 가는 시간은 now까지의 시간과 now에서 해당 노드로 가는 시간의 합이다.
만약 방금 구한 값이 시간배열에 있는 값보다 작다면 최단시간이므로 업데이트 하고 큐에 넣어준다.