[백준 1753] 최단경로

대표적인 다익스트라 알고리즘. c++에서는 우선순위 큐를 사용하고 파이썬에서는 heapq를 사용해주자.

 

이문제가 거지같은점은 cout으로 하면 시간초과나고 printf로 출력하면 통과한다는 것이다.

 

파이썬은 그냥 스무스하게 통과하는데....

 

 

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

using namespace std;
vector<pair<int, int>> adj[20001];
int V, E, s;
#define INF 987654321
bool visit[20001];
void dikjstra(int start) {

	memset(visit, 0, sizeof(visit));
	int dist[20001];
	for (int i = 1; i <= V; i++)dist[i] = INF;
	dist[start] = 0;
	std::priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ dist[start],start });

	while (!pq.empty())
	{
		int cost = pq.top().first;
		int now = pq.top().second;
		pq.pop();
		if (visit[now])continue;
		if (cost > dist[now])continue;
		for (pair<int, int> nextnode : adj[now]) {
			int next = nextnode.first;
			int cost = nextnode.second;
			if (dist[next] > dist[now] + cost) {
				dist[next] = dist[now] + cost;
				if (!visit[next])pq.push({ dist[next],next });
			}
		}
		visit[now] = true;
	}
	for (int i = 1; i <= V; i++) {
		if (dist[i] == INF)printf("INF\n");
		else printf("%d\n", dist[i]);
	}
}



int main() {

	cin >> V >> E>>s;
	for (int i = 1; i <= E; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({ v, w });
	}

	dikjstra(s);


	return 0;
}

 

import sys
import heapq
V, E = map(int,sys.stdin.readline().split())
K = int(input())
edge = [[] for _ in range(V+1)]
for _ in range(E):
    u, v, w = map(int,sys.stdin.readline().split())
    edge[u].append((v,w))


visit = set()
def dikjstra(start):
    heap = []
    dist = [987654321]*(V+1)
    dist[start] = 0
    heap.append((dist[start],start))
    while heap:
        cost, now = list(heapq.heappop(heap))
        if now in visit:
            continue
        if cost > dist[now]:
            continue
        visit.add(now)
        for nextnode in edge[now]:
            if dist[now] + nextnode[1] < dist[nextnode[0]]:
                dist[nextnode[0]]=dist[now]+nextnode[1]
                heapq.heappush(heap,(dist[nextnode[0]],nextnode[0]))

    for i in range(1,V+1):
        if dist[i] == 987654321:
            print("INF")
        else:
            print(dist[i])


dikjstra(K)