관리 메뉴

공부공간

BOJ - 1916 ) 최소비용 구하기 본문

그래프 알고리즘/Dijkstra

BOJ - 1916 ) 최소비용 구하기

SangwonSeo 개발자가될수있을까? 2020. 4. 16. 11:02
728x90


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

 

1916번: 최소비용 구하기

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 M+3째 줄에는 우리가 구하고자 하는 구간

www.acmicpc.net


Dijkstra알고리즘의 기본적인 형태이다. 특정 A번째에서 B번째까지의 최단 경로를 구하기위해서 

 

정수배열에 A번째에서 각 인덱스 번호까지의 최단거리를 갱신시켜주면서 우선순위큐를 비워준다.

 

최단경로가 갱신된다면, 그 때 까지의 누적 경로합을 다시 우선순위큐에 넣어주면서 실행하면된다.

 

 


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 최소비용구하기 {
	public static class node{
		int end, cost;
		public node(int end, int cost) {
			this.end = end;
			this.cost = cost;
		}
	}
	public static void main(String[] args)  throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()); // 도시개수
		 st = new StringTokenizer(br.readLine());
		int m = Integer.parseInt(st.nextToken()); // 버스개수
		
		ArrayList<node> map[] = new ArrayList[n+1];
		for(int i = 1 ; i <= n ; i++) {
			map[i] = new ArrayList<node>();
		}
		
		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());
			map[start].add(new node(end, cost));
		}
		st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		int shortest[] = new int[n+1];
		for( int i = 1 ; i <= n ; i++) {
			shortest[i] = 987654321;
		}
		PriorityQueue<node> pq = new PriorityQueue<>(new Comparator<node>() {
			@Override
			public int compare(node o1, node o2) {
				if( o1.cost > o2.cost) return 1;
				else if( o1.cost < o2.cost) return -1;
				else return 0;
			}
		});
		
		pq.add(new node(start,0));
		shortest[start] = 0;
		
		while(!pq.isEmpty()) {
	
			node now = pq.poll(); // 간선이 작은 상태로만 정렬
			int target = now.end;
			int target_cost = now.cost;
			
			if(shortest[target] < target_cost) continue;
			int size = map[target].size();
			for(int i = 0 ; i < size ; i++) {
				
				int next = map[target].get(i).end;
				int next_cost = map[target].get(i).cost;
				
				if(shortest[next] > shortest[target] + next_cost) {
					shortest[next] = shortest[target] + next_cost;
					pq.add(new node(next ,shortest[target] + next_cost ));
				}
			}
		}
		System.out.println(shortest[end]);
	}
}

728x90

'그래프 알고리즘 > Dijkstra' 카테고리의 다른 글

BOJ - 10282 ) 해킹  (0) 2020.10.30
BOJ - 1167 ) 트리의 지름  (0) 2020.10.25
BOJ - 1504 ) 특정한 최단 경로  (0) 2020.08.24
BOJ - 1261 ) 알고스팟  (0) 2020.04.16
BOJ - 1916 ) 최소비용 구하기  (0) 2020.04.16
BOJ - 1753 ) 최단경로  (0) 2020.04.07
0 Comments
댓글쓰기 폼