백준 1238 파티 C++

백준 지문

---

 

접근법

최단 거리를 구하는 문제이므로 다익스트라를 사용하면 된다.

---

풀이

1. 시간 복잡도 : 정점의 개수가 최대 1000개, 간선의 개수가 최대 10000개 이므로 O([V][E]) = 10'000'000이 되어 시간 내에 풀 수있다.

2. 모든 정점이 X로가는 최소시간을 구한다.

3. X에서 모든 정점으로 가는 최소시간을 구한다.

#include <vector>
#include <iostream>
#include <cmath>
#include <queue>

using namespace std;

const int INF = 1e9+7;
#define PP pair<int, int>
vector<pair<int, int>> road[1001];
vector<int> dist;
int sum[1001];

int N, M, X;

void dijkstra(int s)
{
    dist.clear();
    dist.resize(1001, INF);
    
    dist[s] = 0;
    priority_queue<PP, vector<PP>, greater<PP>> pq;
    
    pq.push({0, s});
    
    while(!pq.empty())
    {
        int t = pq.top().first;
        int current = pq.top().second;
        pq.pop();
        
        if(t > dist[current]) continue;
        
        for(int i = 0; i < road[current].size(); ++i)
        {
            int next_time = t + road[current][i].first;
            int next = road[current][i].second;
            
            if(next_time < dist[next])
            {
                dist[next] = next_time;
                pq.push({next_time, next});
            }
        }
    }
}

int main()
{
    cin >> N >> M >> X;
    int answer = 0;
    
    int start, end, t;
    
    for(int i = 0; i < M; ++i)
    {
        cin >> start >> end >> t;
        road[start].push_back({t , end});
    }
    
    for(int i = 1; i <= N; ++i)
    {
        dijkstra(i);
        sum[i] = dist[X];
    }
    dijkstra(X);
    
    for(int i = 1; i <= N; ++i)
    {
        sum[i] += dist[i];
        answer = max(sum[i], answer);
    }
    
    cout << answer;
    return 0;
}

---

최적화

도로를 입력 받을 때 정방향과 역방향을 받고, 모든 정점에서 X로 가능 경우와 X에서 모든 정점으로 가는 경우를 구한다.

단방향이기 때문에 그래프, 거리 배열을 2개의 경우로 나눠야한다!

#include <vector>
#include <iostream>
#include <cmath>
#include <queue>

using namespace std;

const int INF = 1e9+7;
#define PP pair<int, int>
vector<pair<int, int>> road[2][1001];
vector<int> dist[2];
int sum[1001];

int N, M, X;

void dijkstra(int k)
{
    dist[k].resize(1001, INF);
    
    dist[k][X] = 0;
    priority_queue<PP, vector<PP>, greater<PP>> pq;
    
    pq.push({0, X});
    
    while(!pq.empty())
    {
        int t = pq.top().first;
        int current = pq.top().second;
        pq.pop();
        
        if(t > dist[k][current]) continue;
        
        for(int i = 0; i < road[k][current].size(); ++i)
        {
            int next_time = t + road[k][current][i].first;
            int next = road[k][current][i].second;
            
            if(next_time < dist[k][next])
            {
                dist[k][next] = next_time;
                pq.push({next_time, next});
            }
        }
    }
}

int main()
{
    cin >> N >> M >> X;
    int answer = 0;
    
    int start, end, t;
    
    for(int i = 0; i < M; ++i)
    {
        cin >> start >> end >> t;
        road[0][start].push_back({t , end});
        road[1][end].push_back({t , start});
    }
    
    dijkstra(0);
    dijkstra(1);
    
    for(int i = 1; i <= N; ++i)
    {
        answer = max(dist[0][i] + dist[1][i] , answer);
    }
    
    cout << answer;
    return 0;
}