반응형
문제
https://www.acmicpc.net/problem/11779
풀이
다익스트라 알고리즘을 이용하여 최소비용을 구한다. 노드 간의 최단거리가 갱신될 때 부모 노드를 갱신해줘서 도착점과 시작점 사이의 길을 알 수 있게 만든다.
코드
python
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
|
import heapq
n = int(input())
m = int(input())
graph = [[] for _ in range(n + 1)]
INF = int(1e9)
dist = [INF] * (n + 1)
parent = [i for i in range(n + 1)]
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((b, c))
start, end = map(int, input().split())
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
dist[start] = 0
while q:
distance, now = heapq.heappop(q)
if dist[now] < distance:
continue
for i in graph[now]:
cost = distance + i[1]
if cost < dist[i[0]]:
dist[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
parent[i[0]] = now
dijkstra(start)
print(dist[end])
st = []
cnt = 1
i = end
st.append(i)
while i != start:
i = parent[i]
cnt += 1
st.append(i)
print(cnt)
while st:
print(st.pop(), end=' ')
|
cs |
java
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
import java.io.*;
import java.util.*;
public class Main {
static int n, m;
static List<List<Node>> graph;
static int start, end;
static int[] dist;
static int[] parent;
public static void main(String[] args) throws IOException {
input();
dijkstra(start);
solve();
}
private static void solve() throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
bw.write(dist[end] + "\n");
Stack<Integer> st = new Stack<>();
for (int i=end; i!=start; i=parent[i]) {
st.push(i);
}
st.push(start);
bw.write(st.size()+"\n");
while (!st.isEmpty()) {
bw.write(st.pop() + " ");
}
bw.close();
}
private static void dijkstra(int start) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(start, 0));
dist[start] = 0;
while (!pq.isEmpty()) {
Node cur = pq.poll();
int distance = cur.weight;
int now = cur.end;
if (distance > dist[now])
continue;
for (Node nextNode : graph.get(now)) {
int cost = nextNode.weight + distance;
int next = nextNode.end;
if (dist[next] > cost) {
dist[next] = cost;
pq.add(new Node(next, cost));
parent[next] = now;
}
}
}
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
m = Integer.parseInt(br.readLine());
parent = new int[n + 1];
dist = new int[n + 1];
int INF = (int) 1e9;
Arrays.fill(dist, INF);
graph = new ArrayList<>();
for (int i=0; i<=n; i++)
graph.add(new ArrayList<>());
for (int i=0; i<m; i++) {
int a, b, c;
String[] strs = br.readLine().split(" ");
a = Integer.parseInt(strs[0]);
b = Integer.parseInt(strs[1]);
c = Integer.parseInt(strs[2]);
graph.get(a).add(new Node(b, c));
}
String[] strs = br.readLine().split(" ");
start = Integer.parseInt(strs[0]);
end = Integer.parseInt(strs[1]);
br.close();
}
static class Node implements Comparable<Node> {
int end;
int weight;
public Node(int end, int weight) {
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return weight - o.weight;
}
}
}
|
cs |
반응형
'BOJ' 카테고리의 다른 글
백준 2164 - 카드2 (0) | 2022.01.25 |
---|---|
백준 9012 - 괄호 (0) | 2022.01.24 |
백준 1916 - 최소비용 구하기 (0) | 2021.08.11 |
백준 18352 - 특정 거리의 도시 찾기 (0) | 2021.07.19 |
백준 1439 - 뒤집기 (0) | 2021.07.18 |