[プログラマー]タクシー料金の併用

1.問題リンク
2.ココア解説集
1.トラブルシューティング
最小費用経路を求めるアルゴリズムは2つ存在する.

1. 다익스트라 
 = 시작 위치를 기준으로 도착 지점까지 가는데 드는 최소 비용
2. 플로이드 와샬
 = 현재 위치를 기준으로 모든 경로에서 갈 수 있는 최소 비용

Vertex(n)は3以上200以下、Degree(fars)は2以上nx(n-1)/2以下であるため、FloydとShallを選択して問題を解決した.
O(200 x 200 x 200 x 200)なので、完全に時間内に解決できます.
まず,floydとshallによりすべての分岐機構に対して最小経路コストを求める.
そして、始点(s)を基準として、1~nの点(i)を経て、AとBへの経路の最小費用を求める.
min(s->i + i->a + i->b)
2.ソースコード

import java.util.*;
class Solution {
  public static int solution(int n, int s, int a, int b, int[][] fares) {

		int[][] floyd = new int[n][n];
		int INF = 100000000;
		for (int[] f : floyd) {
			Arrays.fill(f, INF);
		}
      for(int i =0 ; i < n ; i++) {
			floyd[i][i] = 0;
		}

		for (int i = 0; i < fares.length; i++) {
			int ss = fares[i][0] - 1;
			int ee = fares[i][1] - 1;
			int c = fares[i][2];

			floyd[ss][ee] = floyd[ee][ss] = c;
		}

      
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
					if (floyd[j][k] > floyd[j][i] + floyd[i][k]) {
						// 직접 가는 것보다 거쳐 가는 경우가 빠른 경우
						floyd[j][k] = floyd[j][i] + floyd[i][k];
					}
				}
			}
		}

		int ans = INF;
		for (int i = 0; i < n; i++) {
			ans = Math.min(ans, floyd[s - 1][i] + floyd[i][a - 1] + floyd[i][b - 1]);
		}

		return ans;
	}
}