다익스트라8 BOJ 1854 - K번째 최단경로 찾기(다익스트라) https://www.acmicpc.net/problem/1854 다익스트라 알고리즘을 완전 이해해야 풀 수 있었던 문제. 가중치가 항상 양수이므로 다익스트라 사용 한 도시를 여러번 방문할 수 있다. 이 조건을 명시하지 않아서 조금 어색하게 느껴졌던 것 같다. https://cses.fi/problemset/result/312681/ 유사문제 단방향 가중치 그래프가 주어진다. 1번도시에서 출발하여 i번째 도시로 갈 때 k번째 최단 길이를 찾아라. (중복허용 ex) 2번도시로 가는 길이가 1 3 3 5 이고 k==3이면 답은 3이다.) 우선 나이브하게 접근해보면 dist[i] : 1번도시에서 출발하여 i번째 도시로 가는데 길이를 모두 저장. 위 경우, dist[i]는 pq혹은 set으로 구현할 수 있다. .. 2020. 1. 25. BOJ 1162 - 도로포장 (다익스트라) https://www.acmicpc.net/problem/1162 정점의 상태를 잘 정의하고 정의된 정점 간의 간선이 어떻게 이어져있는지를 잘 파악하면 된다. 양방향 가중치 그래프가 주어진다. 연결된 간선에 대해서 최대 k번 가중치를 0으로 만들 수 있을 때, 정점 1에서 정점n으로 가는 최단길이는? u번 정점 전까지 도로포장을 t번했다면 정점을 (u,t)로 정의한다 (정점의 상태가 최대 20개라서 가능) u->v에 대해 (u,t) -> (v,t), (v,t+1) .. t+1 다익스트라로 풀 수 있다. typedef pair P; typedef pair T; const int MAX = 1e4 + 2; const ll INF = 1e18; vector adj[MAX]; ll dist[MAX][21]; i.. 2020. 1. 25. codeforces #580 div2 D - Shortest Cycle (무방향그래프 사이클, 비둘기집) https://codeforces.com/contest/1206/problem/D undirected graph이고, 최대 1e5개의 정점에 대해 만들어지는 사이클 크기의 최소값을 구하는 문제이다. 오픈카톡에 따르면 무방향그래프에서 사이클을 모두 구하는 것에 대한 알고리즘은 매우 어렵다. ( 불가능하지 않냐고 물어보는 사람도 있었다. ) 하지만 지금 문제에선 사이클 크기의 최소값을 구하는 것이므로 알고리즘을 짤 수 있다. 1) 사이클 크기의 최소값 구하기 서로 연결돼 있는 i,j에 대해, 그 간선을 끊었을 때 i~j의 경로 길이 + 1(자기자신)이 사이클 크기이다. 이를 모든 간선에 대해 적용하며 mn값을 갱신해 나가면 된다. 즉, adj[i][j]=adj[j][i]=0 -> mn = min( dist[.. 2019. 11. 13. 다익스트라 시작점이 정해진 상태이고 가중치>=0일 때 최단경로 구할 때 사용. 사이클이 있어도 사용가능. 하나의 정점을 검사할 때마다 모든 간선에 대해 검사하고, 최소힙(우선순위 큐)에 들어가는 것은 최악의 경우 간선 개수만큼 들어가므로 O(ElogE) bst(set)을 사용해서 유효한 {dist, i}만을 유지한다면 O(ElogV)지만 속도가 크게 차이 안날 뿐더러, 우선순위 큐의 시간복잡도 상수가 더 작다. 구현이 편한 ElogE코드를 사용하자 필요한 것 : bool vst[MAX] {0} int d[MAX] {INF} vector g[MAX] priority queue (dist 가장 가까운 것부터) int main() { bool vst[MAX] = {0}; vector g[MAX]; //{도착지,가중치} .. 2019. 8. 18. 이전 1 2 다음