[Dijkstra] 1238번 파티

1238번 파티

 

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

 

문제

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

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

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

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

 

입력

첫째 줄에 N(1 <= N <= 1,000), M(1 <= M <= 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

 

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

 

예제 입력

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

 

예제 출력

10

 

해결방법

다익스트라 알고리즘(Dijkstra Algorithm)을 통해 최소 비용을 구한다

이 모든 정점에서 목표 정점으로 간 뒤, 다시 돌아와야 한다

 

 

🔥틀렸습니다🔥

모든 1~n 정점의 최소 비용을 모두 구한 다음, 2차원 배열인 dist에 저장하였다

 

그리고 (출발 정점 → 목표 정점) + (목표 정점 → 출발 정점) 의 최소 비용을 더해 최대값을 출력하였다

ans = 0;
for(int i=1; i<=n; i++){
    int d = dist[i][x] + dist[x][i];
    ans = max(ans,d);
}
cout << ans << endl;

 

사실 왜틀렸는지 모르겠다... 테스트케이스도 맞는뎁.... 정답을 알려줭.....😭

 

 

⭐️맞았습니다!!⭐️

최단 경로 강의 영상를 참고했다

 

먼저 모든 노드는 파티가 열리는 목표 노드에 들렸다가 다시 돌아와야한다

만약 2번 노드가 목표 노드일 때, 1번 노드의 경우 왕복 최소 비용은 dist(1→2) + dist(2→1) 인 것이다

이 경우는 1,2,3,4 노드에서 2 노드로 가는 Single-Destination 경로 구하기와 2 노드에서 1,2,3,4 노드로 돌아가는 Single-Source 경로 구하기를 모두 구해야 한다

 

Single-Source의 경우는 one-to-all 을 구하는 다익스트라 알고리즘을 사용하면 된다

하지만 Single-Destination의 경우는 생소하다. 하지만 이 경우는 간단하게 뒤집어서 생각할 수 있다

(1→2)의 경로는 모든 Edge를 뒤집은 (2→1) 의 경로와 같다

따라서 도착 노드를 일반적인 다익스트라 알고리즘으로 한번, 모든 엣지를 뒤집은 다익스트라 알고리즘으로 한번 실행한다

dist1[ ] 과 dist2[ ] 에는 이제 single-source의 경우와 single-destination의 경우의 최단 경로가 저장되어 있다

두 최단 경로를 더해서 최대값을 갖는 경우를 출력하면 된다

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 1001
#define INF 987654321
using namespace std;

int n,m,x;
int u,v,w;
int ans;

typedef pair<int, int> pii;

vector<pii> adj[MAX];
vector<pii> r_adj[MAX];

void dijkstra(int s){
    vector<int> dist1(n+1,INF);
    vector<int> dist2(n+1,INF);
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    
    // 목표 지점에서 돌아오는 길
    pq.push(pii(0,s));
    dist1[s] = 0;
    while(!pq.empty()){
        int pre_d = pq.top().first;
        int pre_v = pq.top().second;
        pq.pop();
        
        if(pre_d > dist1[pre_v]) continue;
        
        for(int i=0; i<adj[pre_v].size(); i++){
            int nxt_v = adj[pre_v][i].first;
            int cost = adj[pre_v][i].second;
            
            if(dist1[nxt_v] > dist1[pre_v] + cost){
                dist1[nxt_v] = dist1[pre_v] + cost;
                pq.push(pii(dist1[nxt_v],nxt_v));
            }
        }
    }
    
    // 목표 지점으로 가는길
    pq.push(pii(0,s));
    dist2[s] = 0;
    
    while(!pq.empty()){
        int pre_d = pq.top().first;
        int pre_v = pq.top().second;
        pq.pop();
        
        if(pre_d > dist2[pre_v]) continue;
        
        for(int i=0; i<r_adj[pre_v].size(); i++){
            int nxt_v = r_adj[pre_v][i].first;
            int cost = r_adj[pre_v][i].second;
            
            if(dist2[nxt_v] > dist2[pre_v] + cost){
                dist2[nxt_v] = dist2[pre_v] + cost;
                pq.push(pii(dist2[nxt_v],nxt_v));
            }
        }
    }
    
    ans = 0;
    for(int i=1; i<=n; i++){
        int d= dist1[i] + dist2[i];
        ans = max(ans,d);
    }
    cout << ans << endl;
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m >> x;
    
    for(int i=0; i<m; i++){
        cin >> u >> v >> w;
        adj[u].push_back(pii(v, w));
        r_adj[v].push_back(pii(u,w));
    }
    
    dijkstra(x);
}