💡 데이크스트라/그래프 이론/최단 경로
Memory 4636KB Time 96ms Code Length 1279B
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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N, M; // 도시 갯수 , 버스 갯수
struct info {
int end, cost;
};
vector<info> bus[1001];
int start_city, end_city;
int visited[1001];
vector<int> dist(1001, 1e9); // Stores the minimum distance from the source
void init() {
cin >> N >> M;
for (int i = 0; i < M; i++) {
int s, e, cost;
cin >> s >> e >> cost;
bus[s].push_back({ e,cost });
}
cin >> start_city >> end_city;
}
void dijkstra(int start) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({ 0, start }); // Start with the source node and distance 0
dist[start] = 0;
while (!pq.empty()) {
int curNode = pq.top().second;
pq.pop();
if (visited[curNode]) continue;
visited[curNode] = 1;
for (const info& edge : bus[curNode]) {
int nextNode = edge.end;
int newDist = dist[curNode] + edge.cost;
if (newDist < dist[nextNode]) {
dist[nextNode] = newDist;
pq.push({ newDist, nextNode });
}
}
}
}
int main() {
init();
dijkstra(start_city);
cout << dist[end_city] << endl;
return 0;
}
이 코드는 다익스트라 알고리즘을 사용하여 주어진 도시 간의 최단 거리를 계산하는 프로그램이다.
init 함수에서는 도시의 갯수(N), 버스의 갯수(M)를 입력받고, 각 도시 간의 버스 정보를 입력받아 저장한다.
dijkstra 함수에서는 우선순위 큐를 이용하여 최단 거리를 계산한다. 시작 도시를 기준으로 다른 도시로 이동할 때의 거리를 계산하고, 이를 업데이트한다.
main 함수에서는 init 함수를 호출하여 초기화를 진행하고, dijkstra 함수를 호출하여 시작 도시부터 목표 도시까지의 최단 거리를 계산한다. 결과를 출력한다.
