[백준 17835] 면접보는 승범이네 (C++)

17835번: 면접보는 승범이네

다익스트라

---

각각의 도시에서 면접장을 가기위한 다익스트라를 매번 돌려선 안된다.

가상의 도시를 하나 잡고 면접장으로 가는 거리를 0으로 두고 우선순위 큐에 넣어준다.

그리고 면접장에서 시작해 모든 도시로 가는 최단거리를 구한다.

이때 주의할 점은 입력을 받을 때 역방향으로 입력 받아야 한다는 점이다.

a -> b가 4

b -> a가 2 이고 면접장이 a라고 하자. b도시에서 면접장을 가는 최소 비용은 2가 되지만 면접장a에서 b로 가는 비용은 4가 된다. 지금은 면접장에서 다른 도시로 가는 최단거리를 통해 답을 구하는 중이다. 따라서 역방향으로 입력을 받아서 인접리스트에 저장하도록 한다.

 

지금까지 구한 최단 거리는 가상의 정점에서 모든 도시로 가는 최단거리를 구한 것이다. 면접장까지의 거리를 0으로 두었기 때문에 반드시 면접장을 지나친 경우를 구한 셈이다. 따라서 최단거리를 모두 살펴보면서 가장 긴 거리를 찾아서 해당 인덱스와 거리를 출력하면 된다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e18
#define pii pair<int, int>
typedef long long ll;
#define pll pair<ll, ll>
// typedef pair<int, int> pii;
 
using namespace std;
 
ll N, M, K, idx;
vector<ll> interview_place;
vector<pll > adj[100001];
ll dist[100001];
 
void input(){
    cin >> N >> M >> K;
    ll u, v, c;
    for(int i = 0; i < M; i++){
        cin >> u >> v >> c;
        adj[v].push_back({c, u});
    }
    for(int i = 0; i < K; i++){
        cin >> u;
        interview_place.push_back(u);
    }
    for(int i = 1; i <= N; i++){
        dist[i] = INF;
    }
}
 
void solve(){
    ll max_cost = 0;
    priority_queue<pll, vector<pll >, greater<pll > > pq;
    for(auto &w: interview_place){
        pq.push({0, w});
        dist[w] = 0;
    }
    
    while(!pq.empty()){
        ll now = pq.top().second;
        ll now_cost = pq.top().first;
        pq.pop();
        
        if(dist[now] < now_cost) continue;
        
        for(int i = 0; i < adj[now].size(); i++){
            ll next = adj[now][i].second;
            ll next_cost = adj[now][i].first + now_cost;
            
            if(dist[next] > next_cost){
                pq.push({next_cost, next});
                dist[next] = next_cost;
            }
        }
    }
    
    for(int i = 1; i <= N; i++){
        if(max_cost < dist[i]){
            idx = i;
            max_cost = dist[i];
        }
    }
    cout << idx << "\n" << max_cost << "\n";
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}​