코딩못하는사람

https://www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 1.접근 간단한 문제인거같아 DFS로 목적지에 도달했을때 stack을 정렬해서 값을 찾아냈는데 시간초과를 받았다.(정렬을 너무 많이 사용하게 되서) 'x원으로 해결이 안되는데 x-1원으로 가능할까?' 라는 질문글에 있던 힌트를 보고 문제를 해결할 수 있었다. 2.풀이 이분탐색을 해가면서 다익스트라를 돌릴때마다 가능한 값이면 정답에 저장하도록 했다. 문제에서..

단일 출발지 최단 경로( Single Source Shortest Path ) 하나의 출발점에서 각 정점까지 도달하는데 비용을 계산하여 최단경로를 구하는 것에는 두가지 다익스트라 알고리즘과 벨만-포드 알고리즘이 있다. 다익스트라와 벨만-포드의 차이는 음의 가중치를 다룰수 있냐 없냐의 차이이다.(벨만-포드가 가능) 다익스트라 알고리즘은 최소힙을 이용하여 구현할 수 있다. 우리가 알아볼 시작지점으로부터 다른 도착지점까지의 가중치 배열을 INF로 초기화한다.ans=[INF]*(v+1) 시작지점의 값을 0으로 초기화하고 heap에 (가중치,위치)을 넣어준다 while문을 사용하여 heappop을 통하여 최소값을 뽑아주고 뽑힌 (가중치+위치에 연결된 곳들의 가중치)로 연결된 곳들을 relax(경로가 더 효율적이면..