ALGORITHM/BOJ
[백준] 1238 파티
0298
2021. 1. 31. 20:08
1238번: 파티
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어
www.acmicpc.net
2021-01-30
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main1238 {
public static int N, M, X, dist[], rdist[];
public static List<List<Party>> list, rlist;
static class Party implements Comparable<Party> {
int v;
int d;
public Party(int v, int d) {
this.v = v;
this.d = d;
}
@Override
public int compareTo(Party o) {
return this.d - o.d;
}
}
public static void solve(List<List<Party>> p, int di[]) {
boolean vtd[] = new boolean[N+1];
PriorityQueue<Party> pq = new PriorityQueue<>();
di[X] = 0;
pq.add(new Party(X, 0));
while(!pq.isEmpty()) {
int cur = pq.poll().v;
if(vtd[cur]) continue; // 방문한적이 있다면 넘어가고
vtd[cur] = true;
for(Party pa: p.get(cur)) { // cur와 연결된 간선들을 체크한다.
if(di[pa.v] > di[cur] + pa.d) { // 그 간선의 현재 dist값보다, dist[cur] + 연결된 값이 더 작으면 교체한다.
di[pa.v] = di[cur] + pa.d;
pq.add(new Party(pa.v, di[pa.v]));
}
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
X = Integer.parseInt(st.nextToken());
list = new ArrayList<>();
rlist = new ArrayList<>();
dist = new int[N+1]; // 파티에서 돌아오는 경우
rdist = new int[N+1]; // 집에서 파티를 참석하러 가는 경우
// 초기화
for(int i = 0; i <= N; i++) {
list.add(new ArrayList<>());
rlist.add(new ArrayList<>());
dist[i] = 987654321;
rdist[i] = 987654321;
}
for(int i = 0; i < M; i++) {
st = new StringTokenizer(bf.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
list.get(a).add(new Party(b, c));
rlist.get(b).add(new Party(a, c));
}
solve(list, dist);
solve(rlist, rdist);
int answer = 0;
for(int i = 1; i <= N; i++)
answer = Math.max(answer, (dist[i] + rdist[i]));
System.out.println(answer);
}
}
|
cs |
#문제풀이
다익스트라 알고리즘 문제이다.
맨 처음에 플로이드-와샬을 생각했지만, 그렇게 풀면 터질 것 같았다.
두 가지 경우를 나눠서 생각하는 것이 포인트이다.
1) 파티(x) -> 집
2 ) 집 -> 파티(X)
파티(X)에서 집으로 가는 경우는 단순하지만, 집에서 파티로 가는 경우를 체크하려면 모든 노드들을 다 한 번씩 체크해야한다. 그래서 역방향으로 가는 list(rlist) 를 하나 새로 만들어주고 X -> 다른 노드들을 체크해주면 된다.