[프로그래머스] 배달 c++

https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스

 

플로이드 워셜 알고리즘 : 모든 지점에서 다른 모든 지점까지 최단 경로를 모두 구하는 알고리즘

풀이 

플로이드 워셜 알고리즘으로 풀었다.
(플로이드 워셜 알고리즘 : 모든 지점에서 다른 모든 지점까지 최단 경로를 모두 구하는 알고리즘)

a->b로 갈때 1~n 사이의 임의의 정수인 k를 들렸다 가는 경우 중에 최솟값으로 비용을 정한다.
각 도시에서 다른 도시까지의 최단거리를 다 계산해서 1번 도시에서 다른 도시까지의  거리가 K 이하일때 answer++해주었다.
초기값은 모든 도시를 다 들리고 비용이 최대일때보다 더 크게 잡았다.

그리고 같은 도시를 연결하는 비용이 여러개 일 수 있으므로 제일 최소일때만 도시 사이의 거리를 갱신해주었다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int solution(int N, vector<vector<int> > road, int K) {
    int answer = 1;
    vector<vector<int> > city(N+1, vector<int>(N+1, 1000000000));
    int road_size=road.size();
    
   for(int i=0;i<road_size;i++)
   {
       if(road[i][2]>city[road[i][0]][road[i][1]])
           continue;
       city[road[i][0]][road[i][1]]=road[i][2];
       city[road[i][1]][road[i][0]]=road[i][2];
   }
    for(int k=1;k<=N;k++){
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
          
            if(i==k || j==k)
                continue;
            city[i][j]=min(city[i][j],city[i][k]+city[k][j]);
            
        }
    }
    }
    for(int i=2;i<=N;i++)
    {
        if(city[1][i]<=K)
        {  
            answer++;
        }
    }
    return answer;
}