1238번 파티

백준 온라인 저지 1238번 파티

---

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

 

1238번: 파티

 

 

 

 

 

풀이 과정

 

 처음 문제를 읽고 최단경로를 구하는 알고리즘이라고 판단했고 가장 쉽게 구현할 수 있는 플로이드-워셜 알고리즘을 생각했습니다. 그러나 정점의 최대 입력이 1000이라는 것을 생각했을 때 O(N^3) 일 경우 시간 초과가 나기 때문에 다익스트라 알고리즘을 사용해야 합니다.

 

 입력받은 정점에 대해서 각각 다익스트라 알고리즘을 수행해야 할지 고민하던 중 입력받은 그래프를 역으로 바꾼 그래프를 만들어 총 2번의 다익스트라 알고리즘을 수행하여 답을 구할 수 있도록 했습니다. 

  1. 처음 입력받은 그래프를 통해 파티 장소에서 마을까지의 최단경로를 계산

  2. 역으로 바꾼 그래프를 통해 각각의 마을에서 파티 장소까지의 최단경로를 계산  

 

 

 

 

 

소스 코드

 

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#define MAX 987654321

using namespace std;
using pp = pair<int, int>;

int n, m, x;

vector<pp> map[1001], reverse_map[1001];
int dist[1001], sum[1001];

void dijkstra(vector<pp> map[1001], int start)
{
    for(int i=0; i<n;i++) {
        dist[i] = MAX;
    }
    dist[start] = 0 ;
    
    priority_queue<pp> pq;
    pq.push(make_pair(0,start));

    while(!pq.empty()) {
        int distance = pq.top().first;
        int vertex = pq.top().second;
        pq.pop();
        if(dist[vertex] < distance) continue;

        for(int i=0; i<map[vertex].size();i++) {
            int v = map[vertex][i].first;
            int d = map[vertex][i].second + distance;

            if( d< dist[v] ) {
                pq.push(make_pair(d,v));
                dist [v] = d;
            }
            
        }
    }

    for(int i=0; i<n;i++) {
        sum[i] += dist[i];
    }

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> x;

    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        
        cin >> a >> b >> c;
        map[a - 1].push_back(make_pair(b - 1, c));
        reverse_map[b - 1].push_back(make_pair(a - 1, c));
    }
    dijkstra(map,x-1);
    dijkstra(reverse_map,x-1);

    int _max =0;
    for(int i=0; i<n;i++) {
        if( i == x-1 ) continue;
        _max = max(_max,sum[i]); 
    }

    cout << _max << endl;
}