[백준] 5972번 택배 배송 (gold 5

import java.io.*;
import java.util.*;

class Point{
    int x;
    int v;
    public Point(int x, int v){
        this.x=x;
        this.v=v;
    }
}

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st=new StringTokenizer(br.readLine());

        int n=Integer.valueOf(st.nextToken());
        int m=Integer.valueOf(st.nextToken());

        ArrayList<Point>[] map=new ArrayList[n+1];
        for(int i=1; i<=n; i++){
            map[i]=new ArrayList<>();
        }

        for(int i=0; i<m; i++){
            st=new StringTokenizer(br.readLine());
            int a=Integer.valueOf(st.nextToken());
            int b=Integer.valueOf(st.nextToken());
            int c=Integer.valueOf(st.nextToken());

            map[a].add(new Point(b,c));
            map[b].add(new Point(a,c));
        }

        int[] num=new int[n+1];
        Arrays.fill(num, Integer.MAX_VALUE);

        PriorityQueue<Point> que=new PriorityQueue<>(new Comparator<Point>(){
            public int compare(Point o1 , Point o2){
                return o1.v-o2.v;
            }
        });

        que.offer(new Point(1,0));

        while(!que.isEmpty()){
            Point temp=que.poll();
            if(temp.v>=num[temp.x]){
                continue;
            }
            num[temp.x]=temp.v;

            for(int i=0; i<map[temp.x].size(); i++){
                Point a=map[temp.x].get(i);
                if(temp.v+a.v >=num[a.x]){
                    continue;
                }
                que.offer(new Point(a.x, temp.v+a.v));
            }
        }
        bw.write(num[n]+"");
        bw.flush();
    }
}

//한 농장에서 다른 농장까지 가면서 마주치는 소의 합이 가장 적은 경우를 구하는 것이다.
//한 지점에서 다른 지점까지의 최단소 여기서 소는 거리의 길이로 생각해도 된다.
//따라서 결국 한 지점에서 다른 한 지점까지의 최단 경로를 구하는 것이므로 다익스트라 알고리즘을
//이용하여 풀이하면 해결이 가능하다.