본문 바로가기

최단경로7

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.
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.
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.

티스토리툴바