본문 바로가기

다익스트라

BOJ #13907 세금 문제 링크 : https://www.acmicpc.net/problem/13907 13907번: 세금 첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D www.acmicpc.net 특정 정점을 방문하는 최단 경로를 구하는 문제이지만, 각 간선들의 통행료를 인상함에 따라 최단 경로가 변경될 수 있음에 유의해야 합니다. dist[i][j] :: 시작 정점으로부터 i번 정점에 도착하기까지 j개의 간선을 이용했을 때의 최소 비용 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1.. 더보기
BOJ #1857 발레리노 문제 링크 : https://www.acmicpc.net/problem/1857 1857번: 발레리노 문제 김주성은 사실 뛰어난 발레 실력을 숨기고 있다. 그는 매일 밤 열심히 발레 연습을 한다. 그는 항상 연습하는 곳의 바닥을 m행 n열의 정사각형 칸들로 나누어 놓고 춤을 춘다. 그가 춤을 추�� www.acmicpc.net dist[x][y] :: 출발점에서 x,y 위치까지 이동하기 위해 사용한 방석의 개수 ans[x][y] :: 출발점에서 x,y 위치까지 이동하기 위해 방석을 배치하는 경우의 수 돌멩이가 없는 각 좌표들에서, DFS를 이용해 '현재 좌표에서 이동할 수 있는 좌표'들을 인접 리스트에 넣어 줍니다. 인접 리스트를 돌며, 아직 방문하지 않은 좌표라면 필요한 방석을 1개씩 더해주며 경로를 .. 더보기

티스토리툴바