최단 경로이다.
특징 :
- 하나의 출발노드에서 다른 모든 노드까지의 최단경로를 구한다.
- 시간복잡도는 O((V+E)logV) 이다.
- 양의 가중치를 가진 간선만 가능하다.
- 최단경로의 부분경로는 역시 최단경로이다.
전반적인 구성 방법은 다른 곳에 널려있으니 그걸 보면 된다.
https://www.acmicpc.net/problem/1753
1753번: 최단경로
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다.
www.acmicpc.net
기준은 해당문제를 잡고 만들었다.
코드 (STL O)
|
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
|
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define INF 987654321
#define pii pair<int, int>
using namespace std;
vector<pii> edge[20001]; // 현재의 거리
int ans[20001];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int v, e, k;
cin >> v >> e >> k;
int st, en, di;
for(int i = 0 ; i < e ; i++)
{
cin >> st >> en >> di;
edge[st].push_back({ en, di });
}
for (int i = 1; i <= v; i++)
{
if (i == k)
ans[i] = 0;
else
ans[i] = INF;
}
priority_queue<pii, vector<pii>, less<pii>> pq; //vertex, cur_dist
// pq에 pii를 줘야 하는것이 내가 잘 실수 하는 부분이다.
// 계속 int로 준다.
pq.push({ k,0 });
while (!pq.empty())
{
pii t = pq.top();
pq.pop();
if (t.second > ans[t.first])
continue;
for (int i = 0; i < edge[t.first].size(); i++)
{
int next = edge[t.first][i].first;
int dist = edge[t.first][i].second;
// 제일 실수 많이 한다.
// t.second+dist < ans[next] 로 많이 했다.
if (ans[t.first] + dist < ans[next])
{
ans[next] = ans[t.first] + dist;
pq.push({ next, ans[t.first] + dist });
}
}
}
for (int i = 1; i <= v; i++)
{
if (ans[i] == INF)
cout << "INF" << '\n';
else
cout << ans[i] << '\n';
}
}
|
cs |
STL(X)
|
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
#include <iostream>
#define INF 987654321
#define pii pair<int, int>
using namespace std;
int ans[20001];
pii pq[100000];
int pq_size = 0;
// cdist기준 최소힙이다.
void pq_add(int node, int cdist)
{
pq[++pq_size] = { node, cdist };
int child = pq_size;
int parent = child / 2;
while (parent >= 1 && pq[parent].second > pq[child].second)
{
swap(pq[parent], pq[child]);
child = parent;
parent = parent / 2;
}
}
pii pq_pop()
{
pii t = pq[1];
pq[1] = pq[pq_size--];
int parent = 1;
int child = parent * 2;
while (1)
{
if (child + 1 <= pq_size && pq[child].second > pq[child + 1].second)
child = child + 1;
if (child > pq_size || pq[parent].second <= pq[child].second)
break;
swap(pq[parent], pq[child]);
parent = child;
child = child * 2;
}
return t;
}
class node
{
public :
int end;
int dist;
node* next;
};
class list
{
public :
node * head = NULL;
node * tail = NULL;
int size = 0;
void add(int en, int di)
{
node* newnode = new node;
newnode->end = en;
newnode->dist = di;
newnode->next = NULL;
size++;
if (head == NULL)
head = newnode;
else
tail->next = newnode;
tail = newnode;
}
void go(pii t)
{
node* show = head;
while (show != NULL)
{
int next = show->end;
int ndist = show->dist;
//t.second 아니라고!!!!!
if (ans[next] > ans[t.first] + ndist)
{
ans[next] = ans[t.first] + ndist;
pq_add( next, ans[t.first] + ndist );
}
show = show->next;
}
}
};
list edge[20001];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int v, e, k;
cin >> v >> e >> k;
int st, en, di;
for(int i = 0 ; i < e ; i++)
{
cin >> st >> en >> di;
edge[st].add(en, di);
}
for (int i = 1; i <= v; i++)
{
if (i == k)
ans[i] = 0;
else
ans[i] = INF;
}
pq_add(k, 0);
while (pq_size != 0)
{
pii t = pq_pop();
if (t.second > ans[t.first])
continue;
edge[t.first].go(t);
}
for (int i = 1; i <= v; i++)
{
if (ans[i] == INF)
cout << "INF" << '\n';
else
cout << ans[i] << '\n';
}
}
|
cs |
대충 둘의 차이는 요정도.