본문 바로가기

다익스트라8

BOJ 2472 - 체인점 (다익스트라, 좌표압축, 세그트리, 수학) https://www.acmicpc.net/problem/2472 이런 문제 3문제를 3시간안에 중학생이 푼다 최대 n개의 정점으로 이뤄진 무방향 가중치 그래프가 주어진다. (n> u >> v >> w; g[u].push_back({ v,w }); g[v].push_back({ u,w }); } memset(d, 0x3f, sizeof(d)); for (int i = 0; i query; while (query--) { int i; cin >> i; cout 2020. 4. 22.
CSES PS - investigation (다익스트라, 위상정렬) https://cses.fi/problemset/task/1202 볼륨이 크다. 사이클이 허용된 가중치가 있는 방향그래프가 주어진다. 시작점 1에서 끝점 n까지 최소 비용으로 이동할 때, (1)그 비용 (2) 가능한 경로의 수, (3) 가능한 경로 중 가장 적은 간선을 지나치는 경우 그 간선의 수, (4) 가장 많은 간선을 지나는 경우 그 간선의 수. (1),(2),(3),(4)를 모두 구하는 문제 (1)은 다익스트라로 풀 수 있고, (2),(3),(4)는 DAG일 때 dp로 풀 수 있는 내용이다. 사이클이 있는 그래프라고 해도 최소비용으로 이동하는 경로는 항상 DAG임이 분명하다. 1. 주어진 그래프에서 유효한 즉, 최소비용 경로에 해당하는 간선들만 남겨서 DAG를 만든다. dist(1~u) + w +.. 2020. 1. 29.
BOJ 5719 - 거의 최단 경로 (다익스트라) https://suuntree.tistory.com/120?category=797985참고 https://www.acmicpc.net/problem/5719 참고 링크에서 설명한 아이디어를 그대로 갖다 사용하면 된다. 최단경로에 포함된 간선을 제외한 그래프에서 최단거리를 구해라 1) 다익스트라https://suuntree.tistory.com/120?category=797985참고 https://www.acmicpc.net/problem/5719 참고 링크에서 설명한 아이디어를 그대로 갖다 사용하면 된다. 출발점 s에서 도착점 e로 갈때, 최단경로에 포함된 간선을 제외한 그래프에서 최단거리를 구해라 1) 다익스트라를 적용해서 dist배열을 초기화 한다. 2) 도착점 부터 역방향 인접배열를 사용해서 모든 .. 2020. 1. 27.
BOJ 10473 - 인간대포 (다익스트라) https://www.acmicpc.net/problem/10473 시작점, 끝점, 대포(최대 100개)의 좌표가 주어진다. 대포를 이용해서 시작점에서 끝점까지 가장 빠르게 이동하는 경우 그 시간을 구해라. 정점의 수가 극히 작으므로, 완전그래프라고 생각하고 풀어보자 정점 u는 좌표 (xu,yu) 정보를 가지고 있다. u->v일 때 가중치는 대포를 타지 않거나 대포를 타는 경우중 짧은 시간. 즉, min(distance(u,v)/5, 2+(distance(u,v)-50)/5) 이다. 단 시작점을 0번, 도착점을 n+1번이라고 할 때, 시작점에선 대포를 탈 수 없음에 유의해야 한다. typedef pair P; //정점의 정의 typedef pair PQ; //for pq const int MAX = 1e.. 2020. 1. 27.

티스토리툴바