백준 1238 파티

문제링크 : https://www.acmicpc.net/problem/1238

아이디어

• X마을에서 각자 돌아가는 것은 다익스트라로 가능
• 그럼 각자 마을에 X 모이는것도 다익스트라로 가능할까?
  • 경로를 반대로 저장해 놓으면 가능
• X에 갈때의 경로와 돌아올때 사용할 경로를 각각 저장
  • X에 갈떄 경로는 다익스트라를 거꾸로 사용하기 위해 경로를 반대로 저장

시간복잡도 계산

• 다익스트라 : O(ElgE)
  • E : M
  • O(MlgM) > 가능

자료구조

• 경로 인접리스트 : vector<pair<int, int>> adj[1010]
  • 비용과 함꼐 입력
    • 다익스트라 비용 리스트 : int dist[1010]
  • 경로의 최대값이 별도로 나와있진 않지만, int로 가능할것으로 예상

코드(C++)

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
typedef pair<int, int> pi2;
 
const int inf = 1e8+10;
int dist[1010];
int dist_rev[1010];
vector<pi2> adj[1010];
vector<pi2> adj_rev[1010];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(dist, dist+1010, inf);
    fill(dist_rev, dist_rev+1010, inf);
    
    int N,M,X; cin >> N >> M >> X;
    for(int i=0; i<M; i++) {
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back(make_pair(c,b));
        adj_rev[b].push_back(make_pair(c,a));
    }
    
    // 가는것 먼저
    priority_queue<pi2, vector<pi2>, greater<pi2>> pq;
    
    // 도착지를 먼저 넣어 거꾸로 수행
    dist_rev[X] = 0;
    pq.push(make_pair(dist_rev[X], X));
    
    while(!pq.empty()) {
        auto eq = pq.top(); pq.pop();
        int ec = eq.first;
        int ei = eq.second;
        if(dist_rev[ei] != ec) continue;
        
        for(auto x : adj_rev[ei]) {
            int nc = x.first;
            int ni = x.second;
            if(dist_rev[ni] > ec + nc) {
                dist_rev[ni] = ec + nc;
                pq.push(make_pair(dist_rev[ni], ni));
            }
        }
    }
    
    // 돌아오는것
    dist[X] = 0;
    pq.push(make_pair(dist[X], X));
    while(!pq.empty()) {
        auto eq = pq.top(); pq.pop();
        int ec = eq.first;
        int ei = eq.second;
        if(dist[ei] != ec) continue;
        
        for(auto x : adj[ei]) {
            int nc = x.first;
            int ni = x.second;
            if(dist[ni] > ec + nc) {
                dist[ni] = ec + nc;
                pq.push(make_pair(dist[ni], ni));
            }
        }
    }
    
    
    // 최대시간구하기
    int maxv = 0;
    for(int i=1; i<=N; i++) {
        maxv = max(maxv, dist[i] + dist_rev[i]);
    }
    
    cout << maxv << '\n';
    
    return 0;
}
 
 

문제유형

• 거꾸로 다익스트라
  • 한점까지 가는데 각각의 비용을 구하
  • 그래프 경로 입력부터 뒤집어서 입력