다익스트라 알고리즘
-
(백준 1238번 파티) 라이님 블로그 대회 알고리즘 따라잡기 16) 다익스트(Dijkstra's Algorithm)PROGRAMMING/알고리즘 2024. 6. 13. 10:59
최단거리 알고리즘 복습 1탄 - 다익스트라 알고리즘 백준 1238번https://www.acmicpc.net/problem/1238 풀이에 중복이 있어 제거하는 풀이를 chatgpt에게 부탁했는데, 두번째 풀이도 바로 챗gpt 풀이다.(gpt가 틀렸길래 디버깅 좀 했쑴ㅎㅎ) 첫번째 풀이다익스트라 알고리즘을 사용해서 all node -> X로 가는 최단 경로를 구한 후(N-1번의 다익스트라 알고리즘 사용) X -> all node로 가는 최단 경로를 구했다.(1번의 다익스트라 알고리즘 사용) 다익스트라 함수를 구현하는데 있어 겹치는 부분이 많아 아쉬운 풀이 #include #include #include #include #include #include using namespace std;typedef pa..
-
(백준 1916번 최소비용 구하기 / 백준 4485번 녹색 옷 입은 애가 젤다지?) 라이님 블로그 대회 알고리즘 따라잡기 16) 다익스트(Dijkstra's Algorithm)PROGRAMMING/알고리즘 2024. 6. 5. 17:09
백준 1916번https://www.acmicpc.net/problem/1916 #include #include #include #include using namespace std;typedef pair P;void dijkstra(int V, int start, int end, const vector>& adj) { vector dist(V, INT_MAX); priority_queue, greater> pq; dist[start] = 0; pq.emplace(0, start); while (!pq.empty()) { int curr_dist = pq.top().first; int curr = pq.top().second; pq.pop(); if (dist[curr] dist[curr] + w..
-
(라이님 블로그 대회 알고리즘 따라잡기 16) 다익스트(Dijkstra's Algorithm)PROGRAMMING/STL 2024. 6. 5. 10:33
D 아이 제이 케이 스트라 알고리즘을 공부해보았다! 이것도 매우 유명한 알고리즘 중 하나! https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220796029558&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 다익스트라 알고리즘(Dijkstra's Algorithm) (수정: 2019-08-16)이제부터 그래프에 대한 글만 엄청 쓸 겁니다. 한 11~12개 정도 예정되어 있네요. 그래프... 정말 어렵고, ...blog.naver.com 라이님 알고리즘을 보다가 gpt가 조금 고쳐준 버전으로 문제를 풀어볼까 한다!#include #include #in..