Algorithm/다익스트라
프로그래머스 합승택시요금 c++ // 다익스트라 table완성 후 조회만, 플로이드
https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 다익스트라 table완성 후 조회만 기존 : 각각 go(start~allnode) + go(allnode, a) + go(allnode , b)하면 시간초과가 난다. int d[3][204]; //[0][node] : 시작~해당정점까지 최단거리 //[1][node] : a~해당정점까지 최단거리 //[2][node] : b~해당정점까지 최단거리 //미리 테이블을 완성후, 쿼리에서는 조회만 하도..
백준 1504 특정한최단경로 c++ // 다익스트라 필수경유정점 해결, INF설정방법
https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 1. INF설정방법 -문제 : INF(987654321) *3 > max_int(21억) -> 오버플로우 -> 오답 최악의경우 : 1 ,2, 3, 4, ... 800개의 정점 비용이모두 최대인경우(1000) == 800*1000 ? 그냥 맘편하게 max_int /3(함수호출 최대횟수)으로 설정하는게 편했다.. 2.의사코드 1~v1~v2~n 1~v2~v1..
백준 1238 파티 c++ // 다익스트라 여러정점 돌리기
https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1. 시간복잡도 다익스트라 : EleE * N(학생마다 다익스트라) * 2(끝~시작지점도 반복) 10000 lg10000 * 1000 *2 가능 2.전체코드 st와 en을 수정하면서 학생마다 다익을 돌린다. #include using namespace std; typedef long long ll; int n, m, x, st, en,ret; vector adj[10..
백준 11779 최소비용구하기2 c++ // 다익스트라 경로복원 방법
https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 1. 다익스트라 경로복원 방법 1.1 pq에 push후 pre배열에 기록하면된다. ex) pre[5]=3 // 5이전에 3임 pre[next.second] = cur.second; //경로복원 : (이전정점을 기록만하면된다) //pre[next.정점]=cur.정점 1.2 출력시 경로를 v 에 push 1.3 reverse(begin,end) 후 출력 cout > m..
백준 1753 최단경로 c++ // 다익스트라 알고리즘
https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. 고찰 정석다익스트라 : O(V^2+E) 우선순위큐 다익스트라 : O(VElgE) 우선순위큐로 풀면된다. 2. 의사코드 1. q.push(0비용,시작정점) 2. 최소거리vertax 선택, 최단거리와다름->무쓸모->continue 3. v의 이웃에 대해, 이웃으로직진 > v로직진+이웃비용 -> 후자가 더짧음 -> d업뎃, q.push 4.while(q.siz..