hades

🥅 문제https://www.acmicpc.net/problem/11657 🔍 설계음수인 간선이 존재하므로, 벨만 포드 알고리즘을 사용해야 한다. 데이크스트라를 이용한다면 음수 간선으로 인해 거리가 음의 무한대로 계속 갱신되어 무한 루프에 빠지게 된다. 기본적인 벨만 포드 식은 Dx(y) = min(Dx(y), Dx(z) + z~y)이다. x에서 y까지의 최소 거리는 x에서 z까지 최소 거리 + z에서 y까지의 거리 중 최솟값이다. 벨만 포드 알고리즘은 벨만 포드 식 적용이 확산된다고 생각하면 된다. 물론, 벨만 포드 알고리즘도 사이클로 인해 음의 무한대가 발생할 수 있다. 정점의 개수가 n이라고 할 때, 한 정점에서 다른 정점들까지의 거리를 모두 갱신하는데는 n-1번 모든 간선에 대해 벨만 포드 식..

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