#[programmers]2021 KAKAKAO BLIND RECRUITMENT-タクシー運賃

1527 ワード

[programmers]2021 KAKAO BLIND RECRUITMENT-タクシー運賃


アイデア

  • fluid-washallアルゴリズムを使用して、各セグメントの費用を事前に計算します.
  • デフォルトでは、
  • から目的地までの料金は
  • です.
  • 経由地を回った後、出発地から経由地、さらに目的地a+経由地、さらに目的地bまで、それぞれの料金よりも安い料金があれば回答に更新します.
  • 正しい(効率100)





    Java Code

    import java.util.Arrays;
    
    class Solution {
        public int solution(int n, int s, int a, int b, int[][] fares) {
            int road = fares.length;
    		int[][] reFares = new int[n+1][n+1];
    		for(int i=0; i<n+1; i++) {
    			Arrays.fill(reFares[i], 1000001);
    		}
    		for(int i=1; i<n+1; i++) {
    			reFares[i][i] = 0;
    		}
    		
    		for(int i=0; i<road; i++) {
    			reFares[fares[i][0]][fares[i][1]] = fares[i][2];
    			reFares[fares[i][1]][fares[i][0]] = fares[i][2];
    		}
    		
    		for(int i=1; i<n+1; i++) {//경
    			for(int j=1; j<n+1; j++) {//출
    				for(int k=1; k<n+1; k++) {//도
    					if(reFares[j][k] > reFares[j][i]+reFares[i][k]) {
    						reFares[j][k] = reFares[j][i]+reFares[i][k];
    					}
    				}
    			}
    		}
    		
    		int answer = reFares[s][a]+reFares[s][b];
    		for(int i=1; i<n+1; i++) {//경
    			if(answer > reFares[s][i] + reFares[i][a] + reFares[i][b]) {
    				answer = reFares[s][i] + reFares[i][a] + reFares[i][b];
    			}
    		}
            
            return answer;
        }
    }