[BOJ] 1916 최소비용 구하기
다익스트라 예제
문제
https://www.acmicpc.net/problem/1916
문제 풀이
package Baekjoon.Graph;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
/**
* Created by kyeahen.
* Title : 1916 최소비용 구하기
* Category : 그래프, 다익스트라
* Date: 2021/06/16
*/
public class BJ_1916 {
static class Edge implements Comparable<Edge> {
int end;
int cost;
Edge(int end, int cost) {
this.end = end;
this.cost = cost;
}
@Override
public int compareTo(Edge o) {
return cost - o.cost;
}
}
static int N, M;
static ArrayList<Edge>[] citys;
static int[] dist;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
citys = new ArrayList[N + 1];
dist = new int[N + 1];
for (int i = 1; i <= N; i++) {
citys[i] = new ArrayList<>();
}
Arrays.fill(dist, Integer.MAX_VALUE);
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
citys[s].add(new Edge(e, c));
}
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
dijkstra(start, end);
}
public static void dijkstra(int start, int end) {
PriorityQueue<Edge> pq = new PriorityQueue<>();
boolean[] visited = new boolean[N + 1];
pq.offer(new Edge(start, 0));
dist[start] = 0;
while (!pq.isEmpty()) {
Edge edge = pq.poll();
int current = edge.end;
if (visited[current]) { continue; }
visited[current] = true;
for (Edge e : citys[edge.end]) {
if (dist[e.end] > dist[current] + e.cost) {
dist[e.end] = dist[current] + e.cost;
pq.offer(new Edge(e.end, dist[e.end]));
}
}
}
System.out.println(dist[end]);
}
}
TMI
21/06/16: 알고리즘 스터디 문제 풀이🤓
댓글남기기