백준 1238번, 파티(C, C++)

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

1238번: 파티

#include<iostream>
#include<vector>
#include<queue>
#include<string.h>

#define INF 100000000
using namespace std;
int N;
int M;
int dist[1001];
vector<pair<int, int>> a[10001];

int dijkstra(int start, int end){
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int>>>pq;
    for(int i = 0; i <= N; i++){
        dist[i] = INF;
    }
    dist[start] = 0;
    pq.push({0, start});
    while(!pq.empty()){
        int cur = pq.top().second;
        int cost = pq.top().first;
        pq.pop();
        if(dist[cur] < cost){
            continue;
        }
        for(int i = 0; i <a[cur].size(); i++){
            int next = a[cur][i].first;
            int ncost = a[cur][i].second;
            if(dist[next] > ncost + cost){
                dist[next] = ncost + cost;
                pq.push({dist[next], next});
            }
        }
    }
    return dist[end];
}
int main(){
    int X;
    int u;
    int v;
    int w;
    int ans = 0;
    int temp;
    cin>>N>>M>>X;
    for(int i = 1; i <= M; i++){
        cin>>u>>v>>w;
        a[u].push_back({v, w});
    }

    for(int i = 1; i<=N; i++){
       temp = dijkstra(i, X) + dijkstra(X, i);
       ans = max(ans, temp);
    }
    cout<<ans;
 
    return 0;
}

다익스트라 알고리즘을 이용한 문제입니다.

 

위 그림은 해당 문제의 예제를 그림으로 표현한 것입니다.

도로들은 단방향입니다.

X가 2라고 주어졌습니다.

2번 정점을 갔다가 다시 원래 정점으로 돌아와야합니다.

 

제일 초기 정점을 1로 잡은 다익스트라 알고리즘에서 dist[2]는 1번 정점이 '2번 정점으로 가는 최소 시간'입니다.

 

2번 정점 시작으로 다익스트라 알고리즘에서 dist[1]은 2번 정점이 1번 정점으로 가는 방법들 중 최소 시간입니다.

 

'1번 정점으로 시작하는 다익스트라 알고리즘 dist[2]의 값' + '2번 정점으로 시작하는 다익스트라 알고리즘 dist[1]의 값'은  1번 마을에 사는 학생이 어떻게든 최소의 시간으로 2번 마을을 들려서 최소의 시간으로 다시 1번 마을로 돌아오는 것입니다.

 

이어서 3번 정점, 4번 정점에서 2번 정점을 오고가는 최소 비용을 구한 다음, 서로를 비교하여 최대 시간을 구합니다.