ALGORITHM/BOJ
[BOJ] 1753 최단경로
0298
2022. 6. 19. 13:34
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
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
69
70
71
72
73
74
75
76
77
78
79
|
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main1753 {
public static int V, E, sx;
public static int[] dist;
public static List<List<Route>> list;
static class Route implements Comparable<Route> {
int v;
int w;
public Route(int v, int w) {
this.v = v;
this.w = w;
}
@Override
public int compareTo(Route o) {
return this.w - o.w;
}
}
public static void solve() {
boolean[] vtd = new boolean[V+1];
PriorityQueue<Route> pq = new PriorityQueue<>();
dist[sx] = 0;
pq.add(new Route(sx, 0));
while(!pq.isEmpty()) {
int cur = pq.poll().v;
if(vtd[cur]) continue;
vtd[cur] = true;
for(Route r: list.get(cur)) {
if(dist[r.v] > dist[cur] + r.w) {
dist[r.v] = dist[cur] + r.w;
pq.add(new Route(r.v, dist[r.v]));
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
V = sc.nextInt();
E = sc.nextInt();
dist = new int[V+1];
list = new ArrayList<>();
for(int i = 0; i <= V; i++) {
list.add(new ArrayList<>());
dist[i] = 987654321;
}
sx = sc.nextInt();
for(int i = 0; i < E; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
int w = sc.nextInt();
list.get(u).add(new Route(v, w));
}
solve();
StringBuilder sb = new StringBuilder();
for(int i = 1; i <= V; i++) {
if(dist[i] == 987654321) sb.append("INF");
else sb.append(dist[i]);
sb.append("\n");
}
System.out.println(sb.toString());
}
}
|
cs |
#문제풀이
다익스트라 문제이다.
