이번에 풀어본 문제는
백준 20182번 골목 대장 호석 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Cost
{
    int n,cost,max;

    public Cost(int n, int cost) {
        this.n = n;
        this.cost = cost;
    }

    public Cost(int n, int cost, int max) {
        this.n = n;
        this.cost = cost;
        this.max = max;
    }
}
public class Main {
    static int N,M,A,B,C;
    static List<List<Cost>> map;
    static int [] min;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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<>();
        min = new int[N+1];
        Arrays.fill(min,Integer.MAX_VALUE);

        for(int i = 0; i <= N; ++i) map.add(new ArrayList<>());
        for(int i = 0; i < M; ++i)
        {
            st = new StringTokenizer(br.readLine());
            int fst = Integer.parseInt(st.nextToken());
            int sec = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            map.get(fst).add(new Cost(sec,cost));
            map.get(sec).add(new Cost(fst,cost));
        }

        PriorityQueue<Cost> pq = new PriorityQueue<>(new Comparator<Cost>()
        {
            @Override
            public int compare(Cost o1, Cost o2)
            {
                if(o1.cost == o2.cost) return o1.n - o2.n;
                return o1.cost - o2.cost;
            }
        });

        boolean [] visited = new boolean[N+1];
        pq.add(new Cost(A,0,Integer.MIN_VALUE));

        while(!pq.isEmpty())
        {
            Cost cur = pq.poll();
            if(visited[cur.n] || cur.n == B) continue;
            visited[cur.n] = true;

            for(Cost next : map.get(cur.n))
            {
                int totalCost = cur.cost + next.cost;
                if(visited[next.n] || totalCost > C) continue;
                int curMax = cur.max;
                if(curMax < next.cost)
                {
                    curMax = next.cost;
                }
                if(min[next.n] > curMax) min[next.n] = curMax;
                pq.add(new Cost(next.n,totalCost,curMax));
            }
        }
        int answer = min[B] != Integer.MAX_VALUE ? min[B] : -1;
        System.out.print(answer);
    }
}

📝 풀이

a에서 b교차로로 이동할 수 있는 모든 경로에서, 한 번에 지불하는 비용의 최댓값들 중 최솟값을 구하는 문제입니다. 총 비용이 c보다 크다면 그 경우는 제외합니다.
다익스트라를 사용하여 a정점에서 b정점까지의 최소 비용의 경로를 구하고, 그 과정에서 발생하는 통행료의 최댓값을 계속 갱신하도록 만들어 보았습니다. 총 통행료가 c를 넘으면 안되므로, 통행료 또한 누적으로 더해줘야 할 것 같습니다.

📜 후기

그냥 해당 정점까지의 최단경로를 구하는 것이 아니라, 경로 내에서 1회 비용의 최댓값과 가진 돈으로 도달할 수 있는지 여부를 확인하며 최단경로가 아니더라도 진행해야하는 조건이 조금 헷갈렸던 문제입니다. 문제 조건을 이해하며 풀다보니 조금 정리가 안된 느낌이고, 제출 시에 부분성공이라고 나와서 다음에 다시 풀어봐야 할 것 같아요!