ALGORITHM/BOJ
[BOJ] 1916 최소비용 구하기
0298
2022. 6. 19. 14:48
https://www.acmicpc.net/problem/1916
1916번: 최소비용 구하기
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그
www.acmicpc.net
2022-06-19
|
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
|
import java.util.*;
public class Main1916 {
public static int N, M;
public static int[] dist;
public static List<List<Bus>> list;
static class Bus implements Comparable<Bus> {
int v;
int w;
public Bus(int v, int w) {
this.v = v;
this.w = w;
}
@Override
public int compareTo(Bus o) {
return this.w - o.w;
}
}
public static void solve(int sx) {
boolean[] vtd = new boolean[N+1];
PriorityQueue<Bus> pq = new PriorityQueue<>();
pq.add(new Bus(sx, 0));
dist[sx] = 0;
while(!pq.isEmpty()) {
int cur = pq.poll().v;
if(vtd[cur]) continue;
vtd[cur] = true;
for(Bus b: list.get(cur)) {
if(dist[b.v] > dist[cur] + b.w) {
dist[b.v] = dist[cur] + b.w;
pq.add(new Bus(b.v, dist[b.v]));
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
dist = new int[N+1];
list = new ArrayList<>();
Arrays.fill(dist, 987654321);
for(int i = 0; i <= N; i++) list.add(new ArrayList<>());
for(int i = 0; i < M; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
list.get(a).add(new Bus(b, c));
}
int sx = sc.nextInt();
int sy = sc.nextInt();
solve(sx);
System.out.println(dist[sy]);
}
}
|
cs |
#문제풀이
다익스트라 문제이다
