백준 No.14284 간선 이어가기2 - JAVA

문제

정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선 리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. 이때, 특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것이다. 연결이랑 두 정점이 간선을 통해 방문 가능한 것을 말한다.

s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가하는 간선의 순서를 조정할 때, 그 최솟값을 구하시오.

 

 

 

키워드

s와 t가 연결이 되는 시점의 간선의 갖우치의 합이 최소가 되게 추가하는 간선의 순서를 조정할 때 그 최솟값을 구하시오

-> 다익스트라인데 여기서 s 정점에서 t정점에 가는 간선 중에 최단 경로를 구하라는 것인데 무방향이라 코드에서는 양방향으로 구현했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static int dist[];
    static ArrayList<ArrayList<Vertex>> graph = new ArrayList<>();

    static int N,M;

    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());

        dist = new int[N+1];
        for (int i = 0; i < N+1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < M ; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            graph.get(start).add(new Vertex(end,cost));
            graph.get(end).add(new Vertex(start,cost));
        }

        st = new StringTokenizer(br.readLine());

        int s = Integer.parseInt(st.nextToken());
        int t= Integer.parseInt(st.nextToken());

        System.out.println(solution(s,t));
    }


    static int solution(int s,int t){
        Arrays.fill(dist,Integer.MAX_VALUE);
        PriorityQueue<Vertex> queue = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        queue.add(new Vertex(s,0));

        dist[s] = 0;

        while(!queue.isEmpty()){
                Vertex now = queue.poll();

                for(Vertex next : graph.get(now.v)){
                    if(dist[next.v] > dist[now.v] + next.cost){
                        dist[next.v] = dist[now.v] + next.cost;
                        queue.add(new Vertex(next.v,dist[next.v]));
                    }
                }
        }

        return dist[t];
    }

    static class Vertex{
            int v;
            int cost;

            public Vertex(int v,int cost){

                this.v = v;
                this.cost = cost;
            }
    }
}