1238 파티

www.acmicpc.net/problem/1238

1238번: 파티

처음엔 플로이드 와샬 문제인 줄 알았지만 \( 1 \leq N \leq 1000 \) 이라 고민을 많이 했던 문제.

 

플로이드 와샬 문제라고 생각한 이유는 각각의 노드부터 x까지의 거리와 x부터 각각의 노드까지의 거리를 알아야 했기 때문이다.

 

단방향 그래프이기 때문에 각각의 노드부터 x까지의 거리와 x부터 각각의 노드까지의 거리가 같지않다.

 

그래서 '거의' 모든 경로를 알아야한다고 생각했지만

다익스트라 알고리즘을 N번하여 원하는 거리만 구할 수 있었다.

 

1.  x 부터 각각의 노드까지의 거리를 구한다.

2. 각각의 노드로부터 x까지의 거리를 구하고 x부터 각각의 노드까지의 거리를 더한다.

3. 최대값을 출력한다.

 

다익스트라 알고리즘을 N번 수행하기 때문에 시간복잡도는 \(  O(N(|E|+|V|log|V|))\) 이 됩니다.

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
 
int dijkstra(int start, int end, vector<vector<pair<int, int>>>& road, vector<vector<int>>& costs)
{
    pq.push({0, start});
    while(!pq.empty())
    {
        int node = pq.top().second, tcost = pq.top().first;
        pq.pop();
        if(costs[start][node] < tcost) continue;
        for(int i=0;i<road[node].size();i++)
        {
            int next = road[node][i].second;
            int tmp = tcost+road[node][i].first;
            if(tmp < costs[start][next])
            {
                costs[start][next] = tmp;
                pq.push({tmp, next});
            }
        }
    }
    return costs[start][end];
}
 
int main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, m, x;
    cin >> n >> m >> x;
    vector<vector<pair<int, int>>> road(n+1, vector<pair<int, int>>());
    int start, end, cost;
    for(int i=0;i<m;i++)
    {
        cin >> start >> end >> cost;
        road[start].push_back({cost, end});
    }
    vector<vector<int>> costs(n+1, vector<int>(n+1, 99999999));
    for(int i=1;i<=n;i++)
        costs[i][i] = 0;
    dijkstra(x, 0, road, costs);
 
    int mx = 0;
    for(int i=1;i<=n;i++)
    {
        if(i == x) continue;
        costs[x][i] += dijkstra(i, x, road, costs);
        mx = max(mx, costs[x][i]);
    }
    cout << mx;
 
    return 0;
}