728x90
https://www.acmicpc.net/problem/20168
https://www.notion.so/1f167f8e832781bfa0f3ce36f0c51641
오늘 문제는 오랜만에 다익스트라!!
풀 수 있는 방법은 백트래킹, 다익스트라 등 여러 방법이 존재한다.
다만 문제에 오류가 있는 듯 하다.
7 7 1 6 4
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
1 7 2
7 5 1
위의 테스트 케이스로 2가 나와야 정상이다.
다만 스터디원의 한분은 -1이 나왔지만 테스트를 통과하였다.
import java.io.*;
import java.util.*;
public class Main {
public static ArrayList<ArrayList<int[]>> map = new ArrayList<>();
public static int N, M, A, B, C;
public static int[] visited;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
input(br);
pro();
}
static void pro() {
PriorityQueue<int[]> pq = new PriorityQueue<>(
(x, y) -> Integer.compare(x[1], y[1])
);
pq.add(new int[]{A,0,0});
while(!pq.isEmpty()){
int[] cur = pq.poll();
int x = cur[0];
int fee = cur[1];
int total = cur[2];
if(x == B){
System.out.println(fee);
return;
}
if(visited[x] < total) continue;
visited[x] = total;
for(int[] route : map.get(x)){
int nx = route[0];
int nf = Math.max(fee, route[1]);
int nt = total + route[1];
if(nt > C) continue;
// System.out.println(x + "->" + nx +" :"+ nt + " " + nf);
pq.add(new int[]{nx, nf, nt});
}
}
System.out.println(-1);
}
static void input(BufferedReader br) throws Exception {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = Integer.parseInt(st.nextToken());
B = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new ArrayList<>();
visited = new int[N+1];
for(int i = 0; i <= N; i++){
map.add(new ArrayList<>());
visited[i] = Integer.MAX_VALUE;
}
for(int i=0 ; i<M ; i++){
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
map.get(a).add(new int[]{b,c});
map.get(b).add(new int[]{a,c});
}
}
}
위의 코드는 나의 코드인데 스터디원과 다른 부분은 visited 부분이다.
나는 visited 체크를 int로 해서 거리가 visited보다 크면 continue해주었다.
그래서 나는 2로 정답이 나왔다.
흠.. 여기서 더 예외 케이스가 있을지 궁금하다!
728x90
'coding test > baekjoon' 카테고리의 다른 글
| [baekjoon] 21277 짠돌이 호석 - 90도 회전, 겹치는 부분 확인(왼,위도 확인 필요) (0) | 2025.05.30 |
|---|---|
| [baekjoon] 1495. 기타리스트 - dp 값 범위 보고 유추해보기 (0) | 2025.05.28 |
| [baekjoon] 21275 폰 호석만 - 진법 변환 (0) | 2025.05.23 |
| [baekjoon] 9489 사촌 - 메모리 초과/NoSuchElement (2) | 2025.05.21 |