|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
class Solution {
public int solution(int n, int s, int a, int b, int[][] fares) {
int answer = 0;
int[][] distance = new int[n+1][n+1];
// 거리 초기화
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(i == j)
distance[i][j] = 0;
else
distance[i][j] = n * 100000 + 1;
}
}
for(int i=0;i<fares.length;i++) {
int src = fares[i][0];
int des = fares[i][1];
int fare = fares[i][2];
distance[src][des] = distance[des][src] = fare;
}
// 각 정점에서의 최단 경로 갱신
for(int k=1;k<=n;k++) {
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(distance[i][j] > distance[i][k] + distance[k][j])
distance[i][j] = distance[i][k] + distance[k][j];
}
}
}
// 각 정점을 합승 지점으로 잡고 계산하여 최소 요금 갱신
answer = distance[s][1] + distance[1][a] + distance[1][b];
for(int i=2;i<=n;i++) {
if(answer > distance[s][i] + distance[i][a] + distance[i][b])
answer = distance[s][i] + distance[i][a] + distance[i][b];
}
return answer;
}
}
|
cs |
플루이드 워셜 알고리즘을 이용하여 정점에서의 최단 경로를 구하였다.
도달할 수 없는 경우의 경로 값을 정점 * 최대 경로 값 + 1로 설정해주어야 한다.