231106 합승 택시 요금

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;
	}
}

private int max = 20000001;
ArrayList<ArrayList<Edge>> graph;

public int solution(int n, int s, int a, int b, int[][] fares) {
	int answer = max;

	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 = dijkstra(a, n);
	int[] startB = dijkstra(b, n);
	int[] start = dijkstra(s, n);

	for (int i = 1; i <= n; i++)
		answer = Math.min(answer, startA[i] + startB[i] + start[i]);
	return answer;
}

int[] dijkstra(int start, int n) {
	int[] costs = new int[n + 1];
	Arrays.fill(costs, max);

	PriorityQueue<Edge> pq = new PriorityQueue<>();
	pq.offer(new Edge(start, 0));
	costs[start] = 0;

	while (!pq.isEmpty()) {
		Edge now = pq.poll();

		if (now.cost > costs[now.index])
			continue;

		ArrayList<Edge> edges = graph.get(now.index);
		for (Edge edge : edges) {
			int cost = costs[now.index] + edge.cost;

			if (cost < costs[edge.index]) {
				costs[edge.index] = cost;
				pq.offer(new Edge(edge.index, cost));
			}
		}
	}
	return costs;
}

출처:https://school.programmers.co.kr/learn/courses/30/lessons/72413