[백준]K번째 최단경로 찾기(1854)

문제 링크 : [백준]K번째 최단경로 찾기(1854)

1854번: K번째 최단경로 찾기

문제 설명

N개의 노드와 M개의 엣지 정보가 주어졌을 때, 1번에서 각 노드까지의 K번째 최단 거리를 구하세요.

입력

N(노드의갯수, 1 <= N <= 1,000)

M(간선의 갯수, 1 <= M <= 2,000,000)

K(최단 거리 순서,  <= K <= 100)

A_i B_i C_i(간선 정보)

5 10 2
1 2 2
1 3 7
1 4 5
1 5 6
2 4 2
2 3 4
3 4 6
3 5 8
5 2 4
5 4 1

 

출력

-1
10
7
5
14

 

카테고리

#다익스트라

 

시간 복잡도 상한

O(N² * K)

 

해결 방법

1. 다익스트라를 돌리면 한 시작지점에서 모든 지점까지의 최단거리를 구할 수 있습니다.
2. 최단거리만 구할 수 있는 이유는 Visited 배열을 0,1로 저장하기 때문에, 한번이라도 방문했다면, 더이상 방문을 하지 않기 때문입니다.
3. 그리고 그 이후에 다시 방문하게 된다면 우선순위 큐의 특성 상 이전에 방문했던 비용과 같거나 더 큰 비용이 오기 때문에 무시해도 됩니다.
4. 그러나 여기서는 K번째로 작은 비용을 구해야 하기 때문에 Visited배열을 0,1이 아닌 0부터 시작하여 방문 할 때마다 1씩 증가하여 K가 되는 순간을 실제로 방문했다고 취급하게 합니다.
5. 그렇게 되면 K번째로 작은 비용을 구할 수 있습니다.
6. 그러나 다익스트라는 O(간선 * log간선)의 비용이 걸리고, K번 방문하게 하려면 O(간선 * log간선 * K)의 시간복잡도가 발생합니다.
7. 계산해보면 2,000,000 * 21 * 100 = 대략 40억 정도가 되어 시간 초과가 됩니다.
8. 하지만, 잘 뜯어보면 N이 1,000이고 완전 그래프를 생각하더라도 간선의 최대 갯수는 N * (N -1 ) / 2 = 약 50만정도가 됩니다.
9. 결국 나머지는 두 노드를 잇는 중복 간선이 되고, 그 중 최소 비용을 가진 것 외에는 무시해도 되는 값이 됩니다.
10. 따로 처리를 해주어도 좋지만, 우선순위 큐의 성질에 의해 자연스럽게 도태되게 됩니다.
11. 다시 시간복잡도를 계산해보면 500,000 * log500,000 * 100 = 10억이 됩니다.
12. 그리고 실제로는 다익스트라를 한바퀴 돌리더라도 각 노드를 한번 이상씩 방문하기 때문에 10억 이하의 시간복잡도가 됩니다.
13. 더 자세하게 계산하기는 좀 복잡할 거 같아서 여기서 줄입니다.

시간복잡도

O(N² * logN² * K)

코드

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int n,m,k,c[1001],i,j,z;
int d[1001];
vector<pair<int,int> > v[1001];
priority_queue<pair<int,int> > q;
int main(){
	scanf("%d%d%d",&n,&m,&k);
	while(m--){
		scanf("%d%d%d",&i,&j,&z);
		v[i].push_back(make_pair(-z,j));
	}
	c[1]=1;
	for(i=0;i<v[1].size();i++)q.push(v[1][i]);
	i=n;
	while(i&&!q.empty()){
		const int x=q.top().first;
		const int y=q.top().second;
		q.pop();
		if(c[y]>=k)continue;
		c[y]++;
		if(c[y]==k)i--;
		d[y]=-x;
		for(j=0;j<v[y].size();j++){
			if(c[v[y][j].second]<k)q.push(make_pair(v[y][j].first+x,v[y][j].second));
		}
	}
	for(i=1;i<=n;i++)printf("%d\n",(c[i]==k)?d[i]:-1);
}