1238번

1238번 - 파티

처음에 플로이드 알고리즘으로 풀려고 했으나, 시간제한이 넘어갈 것 같아서.. (근데 플로이드 시간 통과된다..)

priority queue 를 이용한 다익스트라 알고리즘을 써서 문제를 풀었다.

X 를 시작점으로 다익스트라를 한번 돌리면, 집에 돌아갈 때 모든 값들을 알 수 있었다.

그리고 나머지 자신의 마을에서 X로 가는 건, 모든 노드에 대해서 다익스트라를 돌렸다..

그리고 그 최단거리 중에서 가장 큰 값을 출력하였다.

## 배운점

어떤 분은 자신의 마을에서 X까지 가는 것을 다익스트라 1번을 돌려서 구하셨다.

방법은 모든 간선의 방향을 뒤집는 것이다. 그러면 출발점을 X로 하는 다익스트라 한번을 통해 모든 마을 까지의 거리를 구할 수 있다.

<정답 코드 - 다익스트라>

#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
const int INF = 987654321;
 
int n, m, x;
vector<vector<pair<int, int>>> v(1001);
 
vector<int> dijkstra(int start)
{
    vector<int> dist(1001);
    for (int i = 1; i <= n; i++)
    {
        dist[i] = INF;
    }
 
    priority_queue<pair<int, int>> pq;
    dist[start] = 0;
    pq.push({start, dist[start]});
 
    while (!pq.empty())
    {
        int now = pq.top().first;
        int cost = -pq.top().second;
        pq.pop();
 
        if (cost > dist[now]) { continue; }
 
        for (int i = 0; i < v[now].size(); i++)
        {
            int next = v[now][i].first;
            int w = v[now][i].second;
 
            if (dist[next] > cost + w)
            {
                dist[next] = cost + w;
                pq.push({next, -dist[next]});
            }
        }
    }
 
    return dist;
}
int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d %d %d", &n, &m, &x);
 
 
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        v[a].push_back({ b,c });
    }
 
    vector<int> fromX = dijkstra(x);
 
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        vector<int> fromN = dijkstra(i);
        ans = ans < (fromN[x] + fromX[i]) ? (fromN[x] + fromX[i]) : ans;
    }
    
    printf("%d\n", ans);
 
    return 0;
}

<정답 코드 - 플로이드 워셜 알고리즘>

#include<iostream>
 
using namespace std;
int D[1001][1001];
const int INF = 987654321;
 
int main()
{
    int n, m, x;
    scanf("%d %d %d", &n, &m, &x);
 
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            D[i][j] = i == j ? 0 : INF;
        }
    }
 
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        D[a][b] = c;
    }
 
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (D[i][j] > D[i][k] + D[k][j])
                {
                    D[i][j] = D[i][k] + D[k][j];
                }
            }
        }
    }
    int ans = 0;
 
    for (int i = 1; i <= n; i++)
    {
        ans = ans < D[i][x] + D[x][i] ? D[i][x] + D[x][i] : ans;
    }
 
    printf("%d\n", ans);
    return 0;
}