[개쉬운 풀이] 백준 1238 파티

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

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

 

입력

 

 

생각

1. 노드와 거리가 있고 최단 거리를 찾는 문제이다. = 다익스트라

2. 가는길과 오는길을 각각 구하여 이 거리가 최대인 값을 구하면 된다.

풀이

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
#define INF 98765432
using namespace std;

const int MAX = 1001;

int N, M, X;
vector<pair<int,int>> v[MAX];
int dist[MAX];

void input(){
    cin >> N >> M >> X;

    for(int i = 0; i < M; i++){
        int start, end, time;
        cin >> start >> end >> time;
        v[start].push_back(make_pair(end, time));
    }
}

//거리 초기화
void init(){
    memset(dist, INF, sizeof(dist));
}

int process(int start, int end){

    int result = 0;
	
    //거리 초기화
    init();
    dist[start] = 0;
    //우선순위 큐를 활용하여 구현한다. O(nlogn)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;
    pq.push(make_pair(0, start)); //(거리, 노드)로 큐에 넣어야 거리가 작은 순서대로 pop할 수 있다.
    dist[start] = 0;

    while(!pq.empty()){
        int current = pq.top().second;
        int distance = pq.top().first;
        
        pq.pop();
        if(current == end){
            result = dist[end];
            break;
        }

        for(int i = 0; i < v[current].size(); i++){
            int next = v[current][i].first;
            int next_distance = v[current][i].second + distance;

            if(dist[next] > next_distance){
                dist[next] = next_distance;
                pq.push(make_pair(next_distance, next));
            }
        }
    }

    return result;
}

void sol(){
    int answer = 0;
    
    for(int i = 1; i <= N; i++){
        init();
        int res = process(i, X) + process(X, i);
        
        if(answer < res){
            answer = res;
        }
    }
    cout << answer << endl;
}

int main(){

    input();
    sol();

    return 0;
}