문제 링크: https://www.acmicpc.net/problem/22116 문제창영이의 퇴근길은 출근길과 조금 다르다. 창영이는 건강을 위해 따릉이를 빌려 타고 퇴근하는 습관을 기르고 있다.창영이의 퇴근길은 N×N 크기의 격자로 표현된다. 창영이는 A1,1에서 출발하여 AN,N까지 이동할 계획이다. 창영이는 상하좌우 인접한 격자로 한 번에 한 칸씩 이동할 수 있다. 각 격자 Ar,c에는 자연수가 적혀 있는데, 이는 해당 지역의 높이를 뜻한다. 인접한 격자 사이의 높이 차이의 절댓값을 경사라고 하고, 경사가 클수록 경사가 가파르다고 하자.따릉이는 가격에 따라 성능이 다르다. 비싼 따릉이는 경사가 가파르더라도 내리지 않고 타고 갈 수 있지만, 값싼 따릉이는 경사가 가파르면 힘들고 위험하기 때문에 내려서..

문제 링크: https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 문제 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재한다. 각각 도시는 1번부터 N번까지 번호가 붙여져 있다. 그 중에서 1번 도시의 군주 박건은 모든 도시를 정복하고 싶어한다. 처음 점거하고 있는 도시는 1번 도시 뿐이다. 만약 특정 도시 B를 ..