프로그래밍

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

[난이도] level3
[유형] 플로이드 워셜

[풀이]

s에서 어떤 점 k(1~n)까지 같이 타고 갔다고 가정했을 때 요금의 최솟값은
s~k까지의 최단거리 + k~a의 최단거리 + k~b의 최단거리 입니다.
k를 1에서 n까지 바꿔보면서 최단거리를 모두 구해봤을 때의 최솟값이 정답입니다.
모든 점 (i,j)간의 최단거리를 구해야 하므로 플로이드 워셜 알고리즘을 이용하였습니다.

import java.lang.Integer.min
import java.util.*
const val inf = 20000001
var cost = Array(201){IntArray(201){inf} }
class Solution {
    fun solution(n: Int, s: Int, a: Int, b: Int, fares: Array<IntArray>): Int {
        var answer = inf
        for(v in fares){
            cost[v[0]][v[1]]=v[2]
            cost[v[1]][v[0]]=v[2]
        }
        for(i in 1..n) cost[i][i]=0

        for(k in 1..n){
            for(i in 1..n){
                for(j in 1..n){
                    if(cost[i][j] > cost[i][k]+cost[k][j]){
                        cost[i][j] = cost[i][k]+cost[k][j]
                        cost[j][i] = cost[i][j]
                    }
                }
            }
        }
        for(i in 1..n) answer = min(answer, cost[i][s] + cost[i][a] + cost[i][b])

        return answer
    }
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/합승_택시_요금.cpp

www.acmicpc.net/problem/11404

[난이도] Gold4

[유형] 플로이드 워셜

[풀이] 플로이드 워셜

#include <cstdio>
#include <algorithm>
int N,M,dist[101][101],INF=9e8;
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++) {
        for(int j=1;j<=N;j++) {
            dist[i][j] = INF;
            if(i==j) dist[i][j] = 0;
        }
    }
    
    for(int i=0;i<M;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(c < dist[a][b]) dist[a][b] = c;
    }

    for(int k=1;k<=N;k++){
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                dist[i][j] = std::min(dist[i][j],dist[i][k]+dist[k][j]); 
            }
        }
    }

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            printf("%d ",dist[i][j]==INF ? 0:dist[i][j]);
        }
        puts("");
    }
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/11404.cpp