728x90
import java.util.*;
class Edge implements Comparable<Edge>{
int index;
int cost;
Edge(int index, int cost){
this.index = index;
this.cost = cost;
}
@Override
public int compareTo(Edge e){
return this.cost - e.cost;
}
}
class Solution {
static final int MAX = 20000001; // 200 * 100000 + 1
static ArrayList<ArrayList<Edge>> graph;
public int solution(int n, int s, int a, int b, int[][] fares) {
int answer = Integer.MAX_VALUE;
graph = new ArrayList<>();
for(int i = 0 ; i <= n ; i ++){
graph.add(new ArrayList<>());
}
for(int[] i : fares){
graph.get(i[0]).add(new Edge(i[1], i[2]));
graph.get(i[1]).add(new Edge(i[0], i[2]));
}
int[] startA = new int[n + 1];
int[] startB = new int[n + 1];
int[] start = new int[n + 1];
Arrays.fill(startA, MAX);
Arrays.fill(startB, MAX);
Arrays.fill(start, MAX);
startA = dijkstra(a, startA);
startB = dijkstra(b, startB);
start = dijkstra(s, start);
for(int i = 1; i <= n ; i ++) answer = Math.min(answer, startA[i] + startB[i] + start[i]);
return answer;
}
static int[] dijkstra (int start, int[] costs) {
PriorityQueue<Edge> pq = new PriorityQueue<>();
pq.offer(new Edge(start, 0));
costs[start] = 0;
while (!pq.isEmpty()) {
Edge now = pq.poll();
int nIndex = now.index;
int nCost = now.cost;
if(nCost > costs[nIndex]) continue;
ArrayList<Edge> edges = graph.get(nIndex);
for (Edge edge : edges) {
int cost = costs[nIndex] + edge.cost;
if (cost < costs[edge.index]) {
costs[edge.index] = cost;
pq.offer(new Edge(edge.index, cost));
}
}
}
return costs;
}
}
728x90
'programmers' 카테고리의 다른 글
프로그래머스 3단계 : 1차 셔틀버스 (Java 자바) (1) | 2023.09.14 |
---|---|
프로그래머스 3단계 : 자물쇠와 열쇠 (Java 자바) (0) | 2023.09.14 |
프로그래머스 3단계 : 경주로 건설 (Java 자바) (0) | 2023.09.14 |
프로그래머스 3단계 : 다단계 칫솔 (Java 자바) (0) | 2023.09.13 |
프로그래머스 3단계 : 길 찾기 게임 (Java 자바) (0) | 2023.09.13 |