[JAVA] 백준 14284 - 간선 이어가기 2

https://www.acmicpc.net/problem/14284

정점과 간선 정보가 주어졌을 때 마지막으로 주어지는 시작노드와 종료노드가 이어질 때까지 간선을 하나씩 추가하다가 이어지는 시점의 간선 가중치의 합을 반환하는 문제이다.

결국 이건 시작 노드 -> 종료노드를 최단 경로로 이었을때 가중치의 합과 같으므로 평범한 다익스트라 문제가 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] info = getArray(br.readLine());
        int nodeCount = info[0];
        int vertexCount = info[1];
        int[] dist = new int[nodeCount+1];
        Arrays.fill(dist,Integer.MAX_VALUE);
        List<List<Vertex14284>> list = new ArrayList<>();
        for (int i = 0; i <= nodeCount; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 0; i < vertexCount; i++) {
            int[] v = getArray(br.readLine());
            list.get(v[0]).add(new Vertex14284(v[1],v[2]));
            list.get(v[1]).add(new Vertex14284(v[0],v[2]));
        }

        int[] result = getArray(br.readLine());
        int start = result[0];
        int end = result[1];
        PriorityQueue<Edge2> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[nodeCount+1];
        dist[start] = 0;
        pq.offer(new Edge2(start));
        while(!pq.isEmpty()){
            Edge2 e = pq.poll();
            int v = e.v;
            int weight = dist[v];
            if(visited[v]) continue;
            visited[v] = true;
            if(v==end){
                System.out.println(weight);
                return;
            }
            List<Vertex14284> vList = list.get(v);
            for (int i = 0; i < vList.size(); i++) {
                Vertex14284 vertex = vList.get(i);
                if(vertex.cost+weight< dist[vertex.to]){
                    dist[vertex.to] = vertex.cost+weight;
                    Edge2 offer = new Edge2(vertex.to);
                    offer.weight = dist[vertex.to];
                    pq.offer(offer);
                }
            }
        }
    }
    static boolean check(int i, int j, char[][] map, boolean[][] visited){
        if(i<0||i>=map.length) return false;
        if(j<0||j>=map[0].length) return false;
        if(visited[i][j]) return false;
        return true;
    }

    static int getCost(char c){
        return Character.getNumericValue(c)==1?0:1;
    }
    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class Edge2 implements Comparable<Edge2>{
    int v;
    int weight = 0;
    Edge2(int i){
        this.v = i;
    }
    @Override
    public int compareTo(Edge2 o) {
        return this.weight - o.weight;
    }
}

class Vertex14284{
    int to;
    int cost;
    Vertex14284(int t, int c){
        this.to = t;
        this.cost = c;
    }
}