Question
문제 해설
- N개의 도시 존재
- 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스 존재
- A번째 도시에서 B번째 도시까지 가는데 드는 최소비용은?
- 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수
Solution
풀이 접근 방법
- A번째 도시에서 B번째 도시까지 가는데 드는 최소비용
- 하나의 시작점 -> 다수의 도착지점까지의 최단 거리 => 다익스트라 / 벨만포드 알고리즘
- A부터 모든 노드까지의 최단 거리를 구하고, 거기서 B의 값 리턴
- 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수 -> 음수 없음
- => 다익스트라 알고리즘 사용
정답 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
class Bus implements Comparable<Bus> {
int end, weight;
public Bus(int end, int cost) {
this.end = end;
this.weight = cost;
}
@Override
public int compareTo(Bus o) {
return Integer.compare(this.weight, o.weight);
}
}
public class Main {
static int N;
static ArrayList<Bus>[] busInfo;
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;
N = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
busInfo = new ArrayList[N + 1];
for (int i = 0; i < busInfo.length; i++) {
busInfo[i] = new ArrayList<Bus>();
}
while (m-- > 0) {
st = new StringTokenizer(br.readLine());
int s = Integer.valueOf(st.nextToken());
int e = Integer.valueOf(st.nextToken());
int cost = Integer.valueOf(st.nextToken());
busInfo[s].add(new Bus(e, cost));
}
st = new StringTokenizer(br.readLine());
int start = Integer.valueOf(st.nextToken());
int end = Integer.valueOf(st.nextToken());
int minCost = find(start, end);
bw.write(minCost + "\n");
bw.flush();
bw.close();
}
public static int find(int start, int end) {
int[] dist = new int[N + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue<Bus> pq = new PriorityQueue<Bus>();
pq.add(new Bus(start, 0));
while (!pq.isEmpty()) {
Bus current = pq.poll();
if (current.weight > dist[current.end])
continue;
for (Bus next : busInfo[current.end]) {
int nextEnd = next.end;
int newWeight = dist[current.end] + next.weight;
if (newWeight < dist[nextEnd]) {
dist[nextEnd] = newWeight;
pq.add(new Bus(nextEnd, newWeight));
}
}
}
return dist[end];
}
}