[python] 백준 > 다익스트라 > 최단 거리(1753)

[문제]

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

 

www.acmicpc.net/problem/1753

1753번: 최단경로

[나의 풀이 - 실패버전]

import sys
import heapq
input = sys.stdin.readline

V, E = map(int, input().split())
start_node = int(input())
graph = [[] for _ in range(V+1)]
arr = [list(map(int, input().split())) for _ in range(E)]
for start, end, cost in arr:
    graph[start].append((cost, end))


def dijkstra(s_node, e_node):
    heap = []
    distance = [sys.maxsize for _ in range(V + 1)]
    heapq.heappush(heap, (0, s_node))
    distance[s_node] = 0
    while heap:
        h_cost, h_node = heapq.heappop(heap)
        for c, e in graph[h_node]:
            sum_cost = h_cost+c
            if sum_cost < distance[e]:
                distance[e] = sum_cost
                heapq.heappush(heap, (c, e))
    return distance[e_node]


answer = []
for end_node in range(1, V+1):
    answer = dijkstra(start_node, end_node)
    if answer == sys.maxsize:
        answer = 'INF'
    print(answer)

• while문으로 heap을 돌리면서 heappush를 해줄 때 sum_cost를 넣어줘야 하는데 그냥 c를 넣어줬다.
• 다익스트라 함수를 한번 돌리고 나온 distance에서 값을 출력해주면 되는데 바보같이 매번 다른 end_node에 대한 다익스트라 함수를 매번 호출시켜줬다.

 

[나의 풀이 - 성공버전]

import sys
import heapq
input = sys.stdin.readline

V, E = map(int, input().split())
K = int(input())
distance = [sys.maxsize]*(V+1)
arr = [list(map(int, input().split())) for _ in range(E)]
graph = [[] for _ in range(V+1)]
for start, end, cost in arr:
    graph[start].append((cost, end))
heap = []


def dijkstra(s_node):
    heapq.heappush(heap, (0, s_node))
    distance[s_node] = 0
    while heap:
        h_cost, h_node = heapq.heappop(heap)
        if h_cost > distance[h_node]:
            continue
        for c, e in graph[h_node]:
            sum_cost = h_cost+c
            if sum_cost < distance[e]:
                distance[e] = sum_cost
                heapq.heappush(heap, (sum_cost, e))


dijkstra(K)
for i in range(1, V+1):
    print('INF' if distance[i] == sys.maxsize else distance[i])

 

 

[다른 사람의 풀이(C++)]

#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
int v, e, s, x, y, z, d[20002];
vector<vector<pair<int, int>>> vt;
int main() {
	scanf("%d%d%d", &v, &e, &s);
	vt.resize(v + 1);
	for (int i = 0; i < e; i++) {
		scanf("%d%d%d", &x, &y, &z);
		vt[x].push_back({ y,z });
	}
	memset(d, -1, sizeof(d));
	priority_queue<pair<int, int>> pq;
	pq.push({ 0,s });
	while (pq.size()) {
		int here = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();
		if (d[here] != -1)
			continue;
		d[here] = cost;
		for (auto it : vt[here]) {
			int next = it.first;
			int acost = -it.second - cost;
			if (d[next] != -1)
				continue;
			pq.push({ acost,next });
		}
	}
	for (int i = 1; i <= v; i++) {
		if (d[i] == -1)puts("INF");
		else printf("%d\n", d[i]);
	}
	return 0;
}