[BOJ] 합승 택시 요금

[BOJ] 합승 택시 요금

Problem URL : 합승 택시 요금

#include <vector>
using namespace std;

int adj[201][201];

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            adj[i][j] = 100000 * 200; //  [1]

    for (int i = 1; i <= n; i++) adj[i][i] = 0;

    for (auto fare : fares) {
        adj[fare[0]][fare[1]] = fare[2];
        adj[fare[1]][fare[0]] = fare[2];
    }

    for (int mid = 1; mid <= n; mid++)  // [2]
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                adj[i][j] = min(adj[i][j], adj[i][mid] + adj[mid][j]);

    answer = 1e9;

    for (int i = 1; i <= n; i++)
        answer = min(answer, adj[s][i] + adj[i][a] + adj[i][b]);

    return answer;
}

Comments

[1] 충분히 큰 수로 초기화해줘야 한다.
[2] mid가 가장 바깥 for문인 거 항상 기억하도록 하자!!