백준 BOJ 17835 - 면접보는 승범이네

다익스트라 알고리즘의 활용 문제

처음에는 각 면접장마다 다익스트라를 K번 돌리려고 생각했었는데,

이 경우에는 면접장의 개수가 많기 때문에 TLE를 받게 된다.

 

다익스트라를 한번만 돌리되 처음에 넣는 노드를 K개 넣어주어야 한다.

모든 면접장과 거리 0으로 연결되는 가상의 도시를 하나 만든다고 생각해도 무난하다.

 

다익스트라를 돌리고 난 뒤의 거리는

각 도시에서 가장 가까운 면접장으로 가는 거리값과 같으므로

이 거리 배열을 순회하면서 최대값을 구해주면 AC를 받을 수 있다.

 

이때 주의해야 할 점은 탐색방향이 반대가 되므로

방향그래프의 방향도 모두 뒤집어줘야한다는점?

이거때문에 좀 고생좀했습니다.

 

그리고 범위가 int범위를 넘어갈수있으니 long long 형을 사용해주도록 하자.

#include <bits/stdc++.h>
#define INF 998244353998244353LL
#define x first
#define y second

using namespace std;
typedef long long ll;

vector<pair<ll,int>> graph[123456];
priority_queue<pair<ll,int>> pq;

ll d[123456] = {0};

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	
	for(int i=0; i<123456; i++) d[i] = INF;
	
	int N,M,K;
	int a,b,c,tmp;
	cin >> N >> M >> K;
	
	for(int i=0; i<M; i++){
		cin >> a >> b >> c;
		graph[b].push_back({a,c});
	}
	
	for(int i=0; i<K; i++){
		cin >> tmp;
		d[tmp] = 0;
		pq.push({0,tmp});
	}
	
	while(!pq.empty()){
		ll dist = -pq.top().x;
		int node =  pq.top().y;
		pq.pop();
		
		if(d[node] < dist) continue;
		
		for(auto it : graph[node]){
			int nnode = it.x;
			ll ndist = it.y + dist;
			
			if(d[nnode] > ndist){
				d[nnode] = ndist;
				pq.push({-ndist, nnode});
			}
		}
	}
	
	ll ans = -1;
	int idx = 0;
	for(int i=1; i<=N; i++){
		if(ans < d[i]){
			ans = d[i];
			idx = i;
		}
	}
	
	cout << idx << "\n";
	cout << ans << "\n";
	return 0;
}

골드 2는 살짝 높은감이 있는거같긴한데 일단 G2로 매겨뒀다.

아이디어 자체는 금방 떠올릴수 있었던거같다.