(C++) - 백준(BOJ) 1238번 : 파티

www.acmicpc.net/problem/1238

1238번: 파티

다익스트라 문제였습니다.

 

풀이방법

 i번 친구가 x마을로 가는데 걸리는 최소 시간과 x마을에서 i가 출발해 i마을에 도착하는데 걸리는 최소 시간의 합이 오고 가는데 거리는 총 소요시간이므로 다익스트라로 해당 값을 구해 최댓값을 출력해주면 됩니다.

 

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
using pii = pair<int,int>;
int n, m, x, ans, dist[1001];
vector <pii> graph[1001];

int dijkstra(int start,int end){
    priority_queue <pii,vector<pii>,greater<pii>> pq;
    pq.push({0,start});
    dist[start] = 0;
    while(!pq.empty()){
        int curCost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        if(curCost > dist[cur]) continue;

        for(auto el : graph[cur]){
            int next = el.first;
            int nextCost = el.second;
            if(curCost + nextCost < dist[next]){
                dist[next] = curCost + nextCost;
                pq.push({dist[next],next});
            }
        }
    }
    return dist[end];
}

int main(){
    cin >> n >> m >> x;

    for(int i = 0; i < m; i++){
        int u,v,cost;
        cin >> u >> v >> cost;
        graph[u].push_back({v,cost});
    }

    for(int i = 1; i <= n; i++){
        memset(dist,INF,sizeof(dist));
        int go = dijkstra(i,x);
        memset(dist,INF,sizeof(dist));
        int come = dijkstra(x,i);
        ans = max(ans,go + come);
    }
    cout << ans << '\n';
}