https://www.acmicpc.net/problem/1854
1854번: K번째 최단경로 찾기
첫째 줄에 $n$, $m$, $k$가 주어진다. ($1 ≤ n ≤ 1\,000$, $0 ≤ m ≤ 2\,000\,000$, $1 ≤ k ≤ 100$) $n$과 $m$은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이
www.acmicpc.net
도시의 개수 1000개 도로(에지)의 개수 2000000. 시간 제약 2초
다익스트라 알고리즘으로 접근하자.
근데, 최단 경로가 아닌 k번째 최단 경로
1. 최단 경로를 표현하는 배열을 우선순위 큐 배열로 두자.
이렇게 하면 최단 경로뿐 아니라 최단 경로 ~ k번쨰 최단경로까지 넣을 수 있다.
2. 방문 배열은 쓰지 않는다.
k번쨰 경로를 찾기 위해서는 노드를 여러번 쓰기 떄문
최단 거리 배열 채우기
1. 현재 노드에 저장된 경로가 k개 미만일 때 신규 경로를 추가
2. 경로가 k개일 때 현재 경로 중 최대 경로와 신규 경로를 비교해
신규 경로가 작을 때 업데이트 (우선순위 큐)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;
typedef pair<int, int> edge;
// 그래프 정보 저장 인접 리스트
vector<vector<edge>> mlist;
// 최단 거리 저장 배열
vector<int> mdistance;
int n, m, k;
int w[1004][1004];
priority_queue<int> distqueue[1004];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m >> k;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
w[a][b] = c;
}
priority_queue <edge, vector<edge>, greater<edge>> q;
q.push(make_pair(0, 1)); //first가 가중치, second가 index
distqueue[1].push(0);
while (!q.empty())
{
edge cur = q.top();
q.pop();
for (int adj = 1; adj <= n; adj++)
{
if (w[cur.second][adj] != 0)
{
// 저장된 경로가 k개 안 될 경우 그냥 추가
if (distqueue[adj].size() < k)
{
distqueue[adj].push(cur.first + w[cur.second][adj]);
q.push(make_pair(cur.first + w[cur.second][adj], adj));
}
// 저장된 경로가 k개 이고 현재 가장 큰 값보다 작을 때만 추가
else if (distqueue[adj].top() > cur.first + w[cur.second][adj])
{
distqueue[adj].pop();
distqueue[adj].push(cur.first + w[cur.second][adj]);
q.push(make_pair(cur.first + w[cur.second][adj], adj));
}
}
}
}
for (int i = 1; i <= n; i++)
{
if (distqueue[i].size() == k)
{
cout << distqueue[i].top() << '\n';
}
else
cout << -1 << '\n';
}
return 0;
}
|
cs |