내가보려고만든 메자노트

(정점=노드 같은 뜻! 혼용해서 사용할 시 혼동 방지!) 그래프에서 각 정점끼리 사이의 최단 거리를 구하는 알고리즘 방법은 여러 가지가 있다. 문제에 따라 효율적인 방법이 다르므로 잘 선택해서 사용해야 한다. 문제의 종류 하나의 정점에서 다른 하나의 정점까지 최단 경로를 구하는 문제 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 각 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 응용으로 한 중간 정점을 거쳐서 가는 최단경로 등 다양한 문제의 종류에 적용하여 사용할 수 있다. 알고리즘 종류 하나의 정점에서 다른 모든 정점까지 최단경로를 구하는 문제 -간선의 가중치가 모두 같은 그래프일 경우 BFS -간선의 가중치가 각각 다른 그래프일 경우 다익스트라 벨만-포드 → 음수 가중치..

문제보러가기 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 이문제는 다익스트라의 기본이 되는 문제였다. 알고리즘을 알고는 있었지만 문제를 풀어본 적이 없는 것 같아 기초 문제부터 시작! 문제풀이 -각 노드의 간선 정보를 저장할 list와 출발 노드부터 해당 노드까지의 최소거리를 갱신해주는 배열 dist []를 선언한다. -list의 경우 노드 숫자만큼의 배열과 각 노드의 연결된 노드와 가중치의 정보를 저장할 수 있도록 List list []로 선언해 준다. * Point 2는 노드..