백준 11657번 : 타임머신 / C++
2023. 3. 22. 20:47ㆍ개인공부/코딩테스트
https://www.acmicpc.net/problem/11657
11657번: 타임머신
첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.
www.acmicpc.net
간선중에 음의 간선이 포함되는 경우로 음의 간선 문제를 해결할 수 있는 벨만포드 알고리즘을 공부하고 해결하였다.
|
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>
#define INF 2147483647
using namespace std;
struct edge
{
int start;
int destination;
int cost;
edge(int start, int destination, int cost)
:start(start), destination(destination), cost(cost) {}
};
int N, M;
vector<edge> EdgeList;
long long Dist[501]{};
void Bellman_Ford(int start_point)
{
Dist[start_point] = 0;
for (int j = 0; j < N - 1; ++j)
{
for (int i = 0; i < EdgeList.size(); ++i)
{
edge info = EdgeList[i];
if (Dist[info.start] == INF)
continue;
if (Dist[info.destination] > info.cost + Dist[info.start])
Dist[info.destination] = info.cost + Dist[info.start];
}
}
for (int i = 0; i < EdgeList.size(); ++i)
{
edge info = EdgeList[i];
if (Dist[info.start] == INF)
continue;
if (Dist[info.destination] > info.cost + Dist[info.start])
{
cout << -1;
return;
}
}
for (int i = 2; i <= N; ++i)
{
if (Dist[i] == INF)
cout << -1 << '\n';
else
cout << Dist[i] << '\n';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M;
for (int i = 0; i < M; ++i)
{
int a, b, c;
cin >> a >> b >> c;
EdgeList.push_back(edge(a, b, c));
}
for (int i = 1; i <= 500; ++i)
Dist[i] = INF;
Bellman_Ford(1);
}
|
cs |
'개인공부 > 코딩테스트' 카테고리의 다른 글
| 백준 2573번: 빙산 / C++ (1) | 2023.03.24 |
|---|---|
| 백준 2589번 : 보물섬 / C++ (0) | 2023.03.23 |
| 백준 9370번 : 미확인 도착지 / C++ (0) | 2023.03.21 |
| 백준 1504번 : 특정한 최단 경로 / C++ (0) | 2023.03.20 |
| 백준 1753번 : 최단 경로 / C++ (0) | 2023.03.18 |