[C++] 백준 1238 파티

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

 

최단 시간에 간다 == 학생의 집  ->>  파티를 하는 곳

최단 시간에 온다 == 파티를 하는 곳 ->> 학생의 집

 

최단시간으로 오고가는 거리를 구하기 위해서는 다익스트라를 두번 사용해야한다.

 

1. 파티를 하는곳을 시작점으로 두어 다익스트라 알고리즘 실행

2. 학생의 집을 시작점으로 두어 다익스트라 알고리즘 실행

 

두번 사용한 뒤 각각의 거리를 더해준 값이 최단 시간에 오고간 거리이다.

 

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
int n,m,x;
vector<pair<int,int> > graph[1001];
int d[1001];
int result[1001];
int answer = -1;
 
void init() {
    for(int i=1; i<=n; i++) {
        d[i] = 1000000000;
    }
}
 
void input() {
    cin >> n >> m >> x;
    for(int i=0; i<m; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        graph[a].push_back({b,c});
    }
    init();
}
 
void dijkstra(int start) {
    priority_queue<pair<int,int> > pq;
    d[start] = 0;
    pq.push({0,start});
    
    while(!pq.empty()) {
        int dist = -pq.top().first;
        int now = pq.top().second;
        pq.pop();
        
        if(dist > d[now]) { continue; }
        
        for(int i=0; i<graph[now].size(); i++) {
            int cost = dist + graph[now][i].second;
            
            if(cost < d[graph[now][i].first]) {
                d[graph[now][i].first] = cost;
                pq.push({-cost,graph[now][i].first});                                                                
            }
        }
    }
}
 
void solve() {
    dijkstra(x);
    for(int i=1; i<=n; i++) {
        if(i == x) {continue;}
        result[i] = d[i];
    }
    
    for(int i=1; i<=n; i++) {
        if(i == x) { continue; }
        init();
        dijkstra(i);
        result[i] = result[i] + d[x];
    }
    
    for(int i=1; i<=n; i++) {
        answer = max(result[i],answer);
    }
    cout << answer;
}
 
 
int main() {
    input();
    solve();
}