[프로그래머스] 배달 Python, C++

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

프로그래머스

 

(1) C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<pair<int, int>> V[55];
vector<int> dist;

void dijkstra(int N){
    priority_queue <pair<int, int>> pq;
    pq.push(make_pair(0, 1));
    dist[1] = 0;
    
    while(pq.empty() == 0){
        int cost = -pq.top().first; 
        int cur = pq.top().second; 
        pq.pop();
        
        for(int i = 0; i < V[cur].size(); i++){
            int next = V[cur][i].first;
            int next_cost = V[cur][i].second; 
            if(dist[next] > cost + next_cost){
                dist[next] = cost + next_cost;
                pq.push(make_pair(-dist[next], next));
            }
        }
    }
}

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    dist.resize(N + 1, 2e9);
    for(int i = 0; i < road.size(); i++){
        int a = road[i][0];
        int b = road[i][1];
        int c = road[i][2];
        V[a].push_back(make_pair(b, c));
        V[b].push_back(make_pair(a, c));
    }
    
    
    
    dijkstra(N);
    
    for(int i = 0; i < dist.size(); i++){
        if(dist[i] <= K) answer++;
    }
   
    return answer;
}

(2) Python

import heapq

def dijkstra(dist,adj):
    heap = []
    heapq.heappush(heap, [0,1])
    while heap:
        cost, node = heapq.heappop(heap)
        for c,n in adj[node]:
            if cost+c < dist[n]:
                dist[n] = cost+c
                heapq.heappush(heap, [cost+c,n])


def solution(N, road, K):
    dist = [float('inf')]*(N+1) 
    dist[1] = 0 
    adj = [[] for _ in range(N+1)]  
    for r in road:
        adj[r[0]].append([r[2],r[1]])
        adj[r[1]].append([r[2],r[0]])
    dijkstra(dist,adj)
    return len([i for i in dist if i <=K])