Written by nodejs-style
on 2021-09-06

2021 Kakao blind 72413 - 합승 택시 요금(플로이드-와샬, 완전탐색...

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

- 시작점이 주어져있지만, 경유지가 있기 때문에 모든 경로에 대해서 최단거리를 찾아야되기 때문에 모든 노드 쌍의 최단경로를 찾을 수 있는 플로이드 와샬 알고리즘으로 풀 수 있다. 플로이드 와샬은 한 정점에서 다른 정점을 갈 때 어떤 정점을 거쳐서 가는게 더 빠르다면 기존에 한번에 가는 정점에 거리에 더 짧은 거리값을 계속 업데이트해주는 방식이다.

- 기본 알고리즘만 알면 쉽게 풀 수 있는 문제라고 생각된다. 이게 플로이드 문제구나라고 캐치하는게 어려운 문제이지 캐치해낸다면 금방 푸는 문제 같다.

#include #define INF 4000001 using namespace std; int d[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 (d[i][j] > d[i][k] + d[k][j]) { d[i][j] = d[i][k] + d[k][j]; } } } } } int solution(int n, int s, int a, int b, vector> fares) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i == j) d[i][j] = 0; else d[i][j] = INF; } } for (auto& e : fares) { int u = e[0] - 1, v = e[1] - 1, w = e[2]; d[u][v] = w; d[v][u] = w; } floyd(n); --s, --a, --b; int ans = INF; for (int k = 0; k < n; ++k) { if (ans > d[s][k] + d[k][a] + d[k][b]) { ans = d[s][k] + d[k][a] + d[k][b]; } } return ans; }

from http://ellerymoon.tistory.com/63 by ccl(A) rewrite - 2021-09-06 02:00:19

Top