[프로그래머스] 합승 택시 요금

노드 사이 가중치가 다르다는 점과 최저 택시요금을 구해야 한다는 점에서 다익스트라나 플로이드-와샬을 사용하면 되지 않을까 싶었습니다. 다익스트라보다는 플로이드-와샬이 이해도 더 잘 가고 재미있는 것 같아서 플로이드-와샬을 사용해서 풀었습니다.

풀이 방법

1. 전체적인 틀은 플로이드-와샬 기본 코드를 사용해서 풀었습니다. 백터 전체를 INF로 초기화 한 뒤에 행과 열이 같은 인덱스일 때 0으로 채워줍니다.
2. vector가 2차원이기 때문에 [i][0]은 시작 노드, [i][1]은 도착 노드, [i][2]는 가중치가 됩니다. dist 배열에 아래와 같이 가중치를 대입합니다.
3. 플로이드-와샬 방법을 이용해서 1~n까지 노드 사이의 최단거리를 구합니다.
4. 최종적으로 브루트포스 방식으로 answer를 구합니다. dist[s][i] + dist[i][a] + dist[i][b]에서 i는 거쳐가는 노드를 의미하며 s->i->a로 갈 때 s->i->b로 갈 때 최단거리를 더한 값을 구해줍니다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int INF = 10000000;

void floyd(vector<vector<int>>& dist, int n){
	for (int k = 1; k <= n; k++) {
		//k : 거쳐가는 지점
		for (int i = 1; i <= n; i++) {
			//i : 처음 지점
			for (int j = 1; j <= n; j++) {
				// j : 도착 지점
				if (i == j || i == k || k == j) continue;

				if (dist[i][j] > dist[i][k] + dist[k][j]) dist[i][j] = dist[i][k] + dist[k][j];
				
			}
		}
	}
}
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;
    vector<vector<int>> dist(n+1, vector<int>(n+1, INF));
    
    for (int i = 1; i <= n; i++) dist[i][i] = 0;
    
    for (int i = 0; i < fares.size(); i++) {
		int start = fares[i][0];
		int end = fares[i][1];
		int weight = fares[i][2];

		dist[start][end] = weight;
		dist[end][start] = weight;
	}
    
	floyd(dist, n);
	answer = dist[s][a] + dist[s][b];
	for (int i = 1; i <= n; i++) {
        answer = min(answer,dist[s][i] + dist[i][a] + dist[i][b]);	
	}
    
    
    return answer;
}