백준 1238번: 파티 (C++)

문제링크

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

풀이방법

해당 문제는 플로이드 알고리즘 및 다익스트라 알고리즘 모두 사용하여 해결 할 수 있다.

플로이드 알고리즘

플로이드 알고리즘을 이용하여 쉽게 해결할 수 있다. 풀이 방법은 다음과 같다.

• 플로이드 알고리즘을 통해서 각 노드 사이의 최단거리를 계산 해 놓는다.
• 단 방향이므로 특정 노드에서 특정 노드로 갈 때와 올 때 거리가 다를 수 있으므로 그 두 개를 더한 값을 MAX값과 비교하고, 더 큰 값을 다시 MAX에 저장한다.

위 설명의 시퀀스와 그래프 그림을 통해서 문제를 이해하고 아래 코드를 참고하자.

다익스트라 알고리즘

• solve 함수를 만들어서 st,en인자를 받아서 st부터 en까지 최단 경로를 바로 구할 수 있게 만든다.
• 이를 통해서 solve(st,en)+solve(en,st)값을 통해서 각 학생의 X마을 까지 왕복 거리를 바로 구하고 최댓값을 저장하여 답을 구한다.

코드

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

int n, m, x, a, b, c;
const int INF = 0x3f3f3f3f;
int d[1005][1005];
int max_time;


int main()
{
    cin >> n >> m >> x;
    
    for (int i = 1; i <= n; i++) fill(d[i], d[i] + (n + 1), INF);

    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b],c);  
    }

    for (int i = 1; i <= n; i++) d[i][i] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            
            for (int k = 1; k <= n; k++)
            {
                if (d[j][k] > d[j][i] + d[i][k])
                {
                    d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
                }
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (i == x) continue;
        max_time = max(max_time, d[i][x]+d[x][i]);
    }

    cout << max_time << '\n';
    return 0;
}

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

#define X first
#define Y second

int n, m;

vector<pair<int, int>> adj[1002];
// {거리, 정점 번호}
const int INF = 0x3f3f3f3f;

int solve(int st, int en)
{
    int d[1002];
    fill(d, d + n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
    d[st] = 0;
    // 우선순위 큐에 (0, 시작점) 추가
    pq.push({ d[st],st });
    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop(); // {거리, 정점 번호}    
        // 거리가 d에 있는 값과 다를 경우 넘어감
        if (d[cur.Y] != cur.X) continue;
        for (auto nxt : adj[cur.Y]) {
            if (d[nxt.Y] <= d[cur.Y] + nxt.X) continue;
            // cur를 거쳐가는 것이 더 작은 값을 가질 경우
            // d[nxt.Y]을 갱신하고 우선순위 큐에 (거리, nxt.Y)를 추가
            d[nxt.Y] = d[cur.Y] + nxt.X;
            pq.push({ d[nxt.Y],nxt.Y });
        }
    }
    return d[en];
}


int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int en;
    cin >> n >> m >> en;
   
    int u, v, w;
    while (m--) {
        cin >> u >> v >> w;
        adj[u].push_back({ w, v });
    }
    
    int ans = 0;
    for (int st = 1; st <= n; st++)
        ans = max(ans, solve(st, en) + solve(en, st));
    cout << ans;
}