다익스트라2 [백준 1916] 최소비용 구하기 (C++) https://www.acmicpc.net/problem/1916다익스트라도시를 연결하는 단방향 버스 (출발점, 도착점, 비용)이 주어지고임의의 출발점과 도착점이 주어졌을 때, 이 둘을 잇는 최소 비용을 출력하는 문제 접근방법 음수인 비용이 없어서 다익스트라로 풀어도 된다. (벨만포드로 안풀어도 됨)이거 풀다가 내가 다익스트라를 제대로 이해하고 있는게 맞나 의심했음..다시 공부해야 할 것 같다..다익스트라 기본 개념은 임의의 출발점 하나에 대해 모든 노드에 대한 최소 거리를 저장하고 있는 1차원 배열이 하나 있고,방문한 노드를 하나씩 추가해 가면서 이 배열을 갱신하는 방식이다. 이 문제를 풀 때는,- 인접행렬 (각 노드에 대해 연결된 버스 노선을 담고 있는 2차원 배열. ex. 1번: {(2번도시, 비용.. 2024. 10. 23. [백준 1753] 알고리즘 90일차 : 최단경로 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 C++ 다익스트라 문제가 간결한 것에 비해 걸린 시간이 매우 김. 역시 골드는 만만하게 봐선 안돼 우선순위큐를 사용해서 다익스트라로 풀이하는 문제입니다. 접근방법 인접행렬을 사용했고, 우선순위큐를 사용했습니다. 방문 여부는 큐에서 뽑은 거리가 이미 그 노드까지의 최단경로와 같다면 그 노드에 대해서는 처리하지 않고 넘어가는 식 오답노트 우선순위 큐 안써서 시간초과 났었음 근데 우선순위 .. 2021. 2. 23. 이전 1 다음
