[C++] 프로그래머스 문제풀이 LEVEL 2 배달

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/12978?language=cpp 

프로그래머스

 

 

 

#include <bits/stdc++.h>
using namespace std;

int solution(int N, vector<vector<int> > road, int K) {
    const int INF = 1000000000;
    int answer = 0;
    
    std::vector<std::vector<int>> graph(N + 1, std::vector<int>(N + 1, 0));
    for (int i = 0; i < graph.size(); ++i) {
        for (int j = 0; j < graph[i].size(); ++j) {
            if (i == j) {
                graph[i][j] = 0;
                graph[j][i] = 0;
            } else {
                graph[i][j] = INF;
                graph[j][i] = INF;
            }
        }
    }
    
    for (int i = 0; i < road.size(); ++i) {
        int v1 = road[i][0];
        int v2 = road[i][1];
        int cost = road[i][2];

        graph[v1][v2] = std::min(graph[v1][v2], cost);
        graph[v2][v1] = std::min(graph[v2][v1], cost);
    }
    
    for (int k = 1; k < graph.size(); ++k) {
        for (int i = 1; i < graph.size(); ++i) {
            for (int j = 1; j < graph.size(); ++j) {
                graph[i][j] = std::min(graph[i][j], graph[i][k] + graph[k][j]);
                graph[j][i] = std::min(graph[j][i], graph[j][k] + graph[k][i]);
            }
        }
    }

    for (int i = 1; i < graph.size(); ++i) {
        if (graph[1][i] <= K)
            ++answer;
    }
    return answer;
}