문제이해

아.. 이거 전에 했던 56이랑 완전히 같은 유형 같음.

그리고 애초에 다이젝스트라 정의 : 다익스트라 알고리즘 : 그래프에서 a→b로 가는 최단 거리를 구하는 알고리즘. 이잖아

당연히 다이젝스트라 써야지

코드(1차)

/*
 * 2025-07-24
 * 문제56_백준 1753번
 * */

package day8.B1916;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        int[] start = new int[N];

        List<List<Edge>> graph = new ArrayList<>();
        
        for(int i = 0; i < N; i++){
            graph.add(new ArrayList<>());
        }
        
        StringTokenizer st;
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            
            Edge edge = new Edge(e,w);
            graph.get(s).add(edge);
        }
        
        // 여기부터가 문제야 우선순위 큐 써야하는거같은데

        br.close();
    }
}

**priorityQueue<Integer> q = new PriorityQueue<>();

→ 작은수에서 큰 수 순서대로

2차코드

/*
 * 2025-07-24
 * 문제56_백준 1916번 - 최소비용 구하기
 */

package day8.B1916;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); // 도시 개수
        int M = Integer.parseInt(br.readLine()); // 버스 개수

        List<List<Edge>> graph = new ArrayList<>();

        for (int i = 0; i <= N; i++) { // 1번 도시부터 시작하므로 N+1
            graph.add(new ArrayList<>());
        }

        StringTokenizer st;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            graph.get(s).add(new Edge(e, w));
        }

        // 시작점과 도착점 입력
        st = new StringTokenizer(br.readLine());
        int from = Integer.parseInt(st.nextToken());
        int to = Integer.parseInt(st.nextToken());

        // 다익스트라 알고리즘
        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[from] = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(from, 0));

        while (!pq.isEmpty()) {
            Edge current = pq.poll();
            int now = current.end;

            if (current.weight > dist[now]) continue;

            for (Edge next : graph.get(now)) {
                if (dist[next.end] > dist[now] + next.weight) {
                    dist[next.end] = dist[now] + next.weight;
                    pq.offer(new Edge(next.end, dist[next.end]));
                }
            }
        }

        System.out.println(dist[to]);
        br.close();
    }
}