문제 풀이

전형적인 다익스트라 문제, 비용이 있고 최소비용에 관련된 언급이 있으면 다익스트라를 먼저 생각해보면 좋다.

다익스트라 알고리즘을 사용해서 문제를 푸는 것은 다른 문제에서도 설명을 많이 했었으니까 별도의 설명은 하지 않는다.

다익스트라 알고리즘의 정형화된 방식으로 코드를 짜기만 하면 간단하게 풀 수 있다.

문제 링크

boj/5972

소스코드

PS/5972.java

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	static class Entity implements Comparable<Entity>{
		int c,a;

		public Entity(int c, int a) {
			this.c = c;
			this.a = a;
		}

		@Override
		public int compareTo(Entity o) {
			if(this.c == o.c)
			{
				return a-o.a;
			}
			else
				return c-o.c;
		}
	}
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		List<Entity>[] list = new ArrayList[n+1];
		int []d = new int [n+1];
		Arrays.fill(d,987654321);
		PriorityQueue<Entity> pq = new PriorityQueue<>();
		for(int i=1;i<=n;i++)
			list[i] = new ArrayList<>();
		for(int i=0;i<m;i++)
		{
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b= Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			list[a].add(new Entity(c,b));
			list[b].add(new Entity(c,a));
		}

		pq.add(new Entity(0,1));
		d[1] = 0;
		while(!pq.isEmpty())
		{
			int cur = pq.peek().a;
			int cur_dis = pq.peek().c;
			pq.poll();
			if(cur_dis > d[cur])
				continue;
			for(int i=0;i<list[cur].size();i++)
			{
				int next = list[cur].get(i).a;
				int next_dis =cur_dis + list[cur].get(i).c;
				if(next_dis < d[next])
				{
					pq.add(new Entity(next_dis,next));
					d[next] = next_dis;
				}
			}
		}
		/*for(int i=1;i<=n;i++)
		{
			System.out.print(d[i]+" ");
		}*/
		System.out.println(d[n]);
	}

}