hades

🥅 문제https://www.acmicpc.net/problem/1916 🔍 설계인접 리스트를 활용하여 데이크스트라 알고리즘으로 해결할 수 있다. 다만, 우선순위 큐를 활용하므로, 이미 어느 정점까지 가는데 최소 비용으로 갱신되었을 수도 있으므로, 확인 후 skip하는 것이 필요하다. 그렇지 않으면 인접한 정점까지 반복문을 또 돌게 되어 시간 초과가 발생한다. 👊 풀이#include #include #include #include using namespace std;int n, m, start, endd, cost, a, b;vector>> adj_list(1001);vector dist(1001, 1e9 + 7);priority_queue, vector>, greater>> pq;void Dijk..

🥅 문제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..

🥅 문제https://www.acmicpc.net/problem/1504 🔍 설계1부터 N까지의 경로 중 최단 경로는 다익스트라 알고리즘으로 구할 수 있다. 하지만 두 점을 무조건 지나야 한다. 1부터 어떤 정점까지 최단 경로를 구하고 갱신하는 과정에서 아무런 구분 없이 비용 하나만으로 갱신하면 안된다. 두 점을 지났는지 여부를 알 수 없기 때문이다. 어떤 정점에 도달하기까지 두 점을 지났는지의 여부에 따라 나오는 경우의 수는 아래와 같이 4이다. 0) v1, v2를 모두 지나지 않음1) v2만 지남2) v1만 지남3) v1, v2 모두 지남 따라서 비용을 저장할 때도 4가지 경우로 나누어 저장한다. ★시작점인 1은 v1일 수도 있고, 아닐 수도 있으므로, 경우에 따라 큐에 넣는 초깃값을 잘 넣어야 ..

🥅 문제https://www.acmicpc.net/problem/1238 🔍 설계각 마을에서 x까지의 최단 시간와 x에서 각 마을까지의 최단 시간을 더하면 된다. 플로이드 워셜 알고리즘을 이용해서 모든 마을에서 모든 마을까지의 거리를 구하고, x까지 갔다가 돌아오는 거리의 최단 시간을 갱신하였다. 시간복잡도는 O(V^3)이다.시간 복잡도를 줄이기 위해 O(ElogV)인 다익스트라 알고리즘을 사용할 수 있다. 최종적으로 시간복잡도는 O(VElogV)이다. 👊 풀이1#include #include #include #include using namespace std;vector> dist(1001, vector(1001, 1e9+7));int n, m, x, start, endd, cost, max_co..