#include #include #include #include using namespace std; int number = 6; int INF = 1000000000; vector a[7]; int d[7]; void init() { for (int i = 1; i nextDistance) { d[next] = nextDistance; pq.push({next, nextDistance}); } } } } void printDistance() { for (int i = 0; i < number; i++) printf("%d ", d[i]); } int main(void) { init(); dijkstra(1); printDistance(); return 0; } 코드 참고 : https://blog.na..
[백준/c++] 14938 서강그라운드
✨ 문제 풀이 그래프와, 각 노드를 지나가는 간선의 비용이 있고, 비용의 합에 제한이 있을 때, 어떤 노드에서부터 순회를 시작하면 가장 많은 아이템(노드의 값)을 모을 수 있는지 물어보는 문제로 다익스트라를 이용해서 문제를 해결했다. 내가 해결한 방법은 아래와 같다. 한 노드에 대해서 다익스트라 순회를 한다. 다른 노드까지의 최소 거리를 d 배열에 저장한다. d 배열에 저장된 간선 비용의 합 중에서, m보다 작은 노드들의 아이템 값을 합친다. 모든 노드에 대해서 반복한다. 가장 아이템값이 높은 값을 반환한다. 모든 노드에 대해서 순회하면서 거리의 비용을 계산해야 하므로 매번 다익스트라 순회를 해주기 전, d 배열의 값을 아주 큰 값(1억)으로 초기화해주는 작업을 했다. (최소 거리를 구하는 것이기 때문)..