백준 1753번 : 최단 경로 / C++
2023. 3. 18. 22:45ㆍ개인공부/코딩테스트
1753번: 최단경로
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가
www.acmicpc.net
다익스트라 알고리즘에 대해서 공부하고 다익스트라 알고리즘을 적용하는 문제였다. 다익스트라가 사람이름이라니
첫번째 방법으로는 배열을 이용한 방법이였는데 Next 함수의 시간 복잡도가 O(n) 이여서 정점의 갯수가 많아지면 시간이 너무 오래걸려서 시간초과가 발생하였다. 그래서 처음부터 코드를 다시 작성해서 map 을 이용해서 최솟값을 구하는 시간을 단축해서 문제를 해결하였다.
|
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
|
#include <iostream>
#include <vector>
using namespace std;
#define MAX 10000000
struct Info
{
int vertex;
int value;
Info(int _vertex,int _value)
:vertex(_vertex)
,value(_value)
{}
};
int V, E, K;
vector<Info> vec[20001];
int ans[20001]{};
bool visited[20001]{};
int Next()
{
int nextnum = MAX;
int index = MAX;
for (int i = 1; i <= V; ++i)
{
if (ans[i] != 0 && visited[i] == false && nextnum > ans[i])
{
nextnum = ans[i];
index = i;
}
}
return index;
}
void BFS(int index)
{
visited[index] = true;
int minimum = ans[index];
for (int i = 0; i < vec[index].size(); ++i)
{
Info now = vec[index][i];
if (ans[now.vertex] == 0 && visited[now.vertex] ==false)
ans[now.vertex] = now.value + minimum;
else if (ans[now.vertex] > minimum + now.value)
ans[now.vertex] = minimum + now.value;
}
}
int main()
{
cin >> V >> E >> K;
for (int i = 0; i < E; ++i)
{
int num1, num2, value;
cin >> num1 >> num2 >> value;
vec[num1].push_back(Info(num2, value));
}
BFS(K);
while (true)
{
int index = Next();
if (index == MAX)
break;
BFS(index);
}
for (int i = 1; i <= V; ++i)
{
if (i != K && ans[i] == 0)
cout << "INF" << '\n';
else
cout << ans[i] << '\n';
}
}
|
cs |
|
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
|
#include <iostream>
#include <vector>
#include <map>
using namespace std;
struct Info
{
int edge;
int value;
Info(int _edge, int _value)
:edge(_edge)
,value(_value)
{}
};
int V, E, K;
vector<Info> vec[20001];
bool visited[20001]{};
int ans[20001]{};
multimap<int, int> M;
void BFS()
{
M.insert(make_pair(0, K));
while (!M.empty())
{
auto iter = M.begin();
int index = iter->second;
if (visited[index] == true)
{
M.erase(iter);
continue;
}
visited[index] = true;
for (int i = 0; i < vec[index].size(); ++i)
{
Info info = vec[index][i];
if (ans[info.edge] == 0 && visited[info.edge] == false)
{
ans[info.edge] = ans[iter->second] + info.value;
M.insert(make_pair(ans[info.edge], info.edge));
}
else if (ans[info.edge] > ans[iter->second] + info.value)
{
ans[info.edge] = ans[iter->second] + info.value;
M.insert(make_pair(ans[info.edge], info.edge));
}
}
M.erase(iter);
}
}
int main()
{
cin.tie(NULL);
std::cout.tie(NULL);
ios::sync_with_stdio(false);
cin >> V >> E >> K;
for (int i = 0; i < E; ++i)
{
int u, v, w;
cin >> u >> v >> w;
vec[u].push_back(Info(v, w));
}
BFS();
for (int i = 1; i <= V; ++i)
{
if (ans[i] == 0 && i != K)
cout << "INF" << '\n';
else
cout << ans[i] << '\n';
}
}
|
cs |
'개인공부 > 코딩테스트' 카테고리의 다른 글
| 백준 9370번 : 미확인 도착지 / C++ (0) | 2023.03.21 |
|---|---|
| 백준 1504번 : 특정한 최단 경로 / C++ (0) | 2023.03.20 |
| 백준 1707번: 이분 그래프 / C++ (0) | 2023.03.16 |
| 백준 2206번 : 벽 부수고 이동하기 / C++ (0) | 2023.03.16 |
| 백준 7575번 : 토마토 / C++ (0) | 2023.03.15 |