[프로그래머스][JAVA] 합승 택시 요금 (Graph, DP, Floyd Warshall...

[프로그래머스][JAVA] 합승 택시 요금 (Graph, DP, Floyd Warshall...

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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

import java.util. * ; class Solution { static final int INF = 400 * 100000 ; int [][] Dist = new int [ 200 ][ 200 ]; void floyd( int n){ for ( int k = 0 ; k < n; k + + ){ for ( int i = 0 ; i < n; i + + ){ for ( int j = 0 ; j < n; j + + ){ if (Dist[i][k] + Dist[k][j] < Dist[i][j]){ Dist[i][j] = Dist[i][k] + Dist[k][j]; } } } } } public int solution( int n, int s, int a, int b, int [][] fares) { for ( int i = 0 ; i < n; i + + ){ for ( int j = 0 ; j < n; j + + ){ if (i = = j){ Dist[i][j] = 0 ; } else { Dist[i][j] = INF; } } } for ( int [] edge : fares){ Dist[edge[ 0 ] - 1 ][edge[ 1 ] - 1 ] = edge[ 2 ]; Dist[edge[ 1 ] - 1 ][edge[ 0 ] - 1 ] = edge[ 2 ]; } floyd(n); int answer = INF; s - - ; a - - ; b - - ; for ( int k = 0 ; k < n; k + + ){ answer = Math.min(answer, Dist[s][k] + Dist[k][a] + Dist[k][b]); } return answer; } } Colored by Color Scripter

from http://aig2029.tistory.com/259 by ccl(A) rewrite - 2021-09-08 04:01:30