BOJ 1854 - K번째 최단경로 찾기(다익스트라)

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

다익스트라 알고리즘을 완전 이해해야 풀 수 있었던 문제. 가중치가 항상 양수이므로 다익스트라 사용

한 도시를 여러번 방문할 수 있다. 이 조건을 명시하지 않아서 조금 어색하게 느껴졌던 것 같다.

https://cses.fi/problemset/result/312681/

유사문제

 

<문제설명>

단방향 가중치 그래프가 주어진다. 1번도시에서 출발하여 i번째 도시로 갈 때 k번째 최단 길이를 찾아라.

(중복허용 ex) 2번도시로 가는 길이가 1 3 3 5 이고 k==3이면 답은 3이다.) 

 

<풀이>

우선 나이브하게 접근해보면

dist[i] : 1번도시에서 출발하여 i번째 도시로 가는데 길이를 모두 저장.

 

위 경우, dist[i]는 pq혹은 set으로 구현할 수 있다. 하지만 가능한 길이를 모두 저장하면 메모리 초과가 난다. 

 

따라서, 가장 짧은 길이부터 최대 k개만 저장하도록 한다. 그러면 정답을 출력하는 부분은 다음과 같다.

for (int i = 1; i <= n; i++) {
		if (dist[i].size() < k) cout << -1 << '\n';
		else cout << dist[i].top() << '\n';
}

 

 

dist가 갱신될 때 dist의 크기가 k 미만이면 그냥 추가한다.

dist의 크기가 k이상인 경우엔 dist의 최댓값보다 작은 값이 들어올 경우만 추가후 pop해준다.

for (P p : adj[u]) {
	int v = p.first, w = p.second;
	if (dist[v].size()<k || dist[v].top() > cur + w) {
		if (dist[v].size() == k) dist[v].pop();
		dist[v].push(cur + w);
		pq.push({ cur + w, v });
	}
}

 

 

한 정점이 여러번 갱신되어도 다른 정점을 갱신시킬 여지가 있으므로 체크배열은 사용하지 않는다.

 

<코드>

const int MAX = 1e3 + 3;

priority_queue<int> dist[MAX];
vector<P> adj[MAX];
int main() {
	FAST;
	int n, m, k; cin >> n >> m >> k;
	for (int i = 0, u, v, w; i < m; i++) {
		cin >> u >> v >> w;
		adj[u].push_back({ v,w });
	}

	dist[1].push(0);
	priority_queue<P, vector<P>, greater<P>> pq;
	pq.push({ 0,1 });

	while (!pq.empty()) {
		int u = pq.top().second, cur=pq.top().first;
		pq.pop();

		for (P p : adj[u]) {
			int v = p.first, w = p.second;
			if (dist[v].size()<k || dist[v].top() > cur + w) {
				if (dist[v].size() == k) dist[v].pop();
				dist[v].push(cur + w);
				pq.push({ cur + w, v });
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		if (dist[i].size() < k) cout << -1 << '\n';
		else cout << dist[i].top() << '\n';
	}
}

 

<생각>

한 정점을 여러번 방문할 수 있는데 시간초과가 나지 않는 이유가 뭘까?

다익스트라 과정(pq) 을 많이 하면 할 수록 많은 정점을 방문 하게 되고 경로의 길이가 점점 길어진다.

어느 일정 길이 이상 늘어나면(k값에 따름) 더이상 그 어떤 dist배열도 초기화하지 못하게 되고 pq는 결국 비워진다.