개발_기록용

1. 문제 2. 문제 분석 이름에서 알 수 있듯, 방향 그래프에서의 최단 거리를 구해야 하는 문제이다. 각 edge의 가중치가 양수이므로, 다익스트라 알고리즘을 사용한다! 🎁 방향 그래프에서의 각 edge의 가중치가 음수도 가능하면 벨만-포드 알고리즘을 사용. 3. 풀이 다익스트라 알고리즘 풀이는 2가지 방법이 있다. 쉽게 구현하지만 비효율적. 어렵게 구현하지만 효율적. 전자는 이차원 배열을 이용해 구현하고, 후자는 우선순위 큐를 사용해 구현한다. 이 문제는 시간이 1초로 넉넉치 않으니 우선순위 큐를 사용한 구현 방법을 쓴다! => 각 노드를 보고 난 후의 거리를 저장할 dst 배열도 필요하다! 4. 코드 #include #include #include #define INF 987654321 using ..