목록최단경로 (1)

hades

[Baekjoon] 1753번: 최단경로

🥅 문제https://www.acmicpc.net/problem/1753 🔍 설계adj_matrix를 사용하면, 20000*20000*4Byte로 메모리 초과가 발생한다. adj_list를 사용해야 한다. 우선순위 큐를 이용하여 어떤 점에서 갈 수 있는 점까지의 경로 중 작은 것부터 뽑는다. 이렇게 하면 뒤에 갱신하는 경로의 비용은 앞에 있는 경로의 길이보다 항상 크다. 따라서, 반복문의 최대 횟수는 간선의 개수인 300000이 된다. 👊 풀이#include #include #include #include using namespace std;int n, e, k, u, v, w, result = 0;vector>> adj_list(20001);vector dist(20001, 1e9 + 7);pri..
👊 PS/Algorithm 2024. 8. 5. 20:50
이전 Prev 1 Next 다음