정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. 이때, 특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것이다. 연결이란 두 정점이 간선을 통해 방문 가능한 것을 말한다.
s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가하는 간선의 순서를 조정할 때, 그 최솟값을 구하시오.
k550706 4년 전 1
문제는 아래와 같습니다.
정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. 이때, 특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것이다. 연결이란 두 정점이 간선을 통해 방문 가능한 것을 말한다.
s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가하는 간선의 순서를 조정할 때, 그 최솟값을 구하시오.
예제의 경우
8번과 최초로 연결되는 구간을 살펴보면(특정 정점 s와 t가 연결되는 시점)
아래 소스코드상에서 8번라인(5번노드 -> 8번노드)이 입력되었을떄이고
이때의 최소 가중치의 합은
1->2->5->8로 움직였을때이므로
3+2+6=11입니다
근데 예제의 답은 5로 되어있습니다
내용을 읽어봤을땐 하나의 간선을 추가할때마다 데이크스트라를 돌려야 하는거 같은데,
혹시나해서 답을 제출해보니 단순 데이크스트라를 돌리면 정답으로 처리 되어있습니다.
문제를 읽어보면 간선 m개가 있는데, 이 중에 하나씩 추가를 하면서
그때마다 데이크스트라를 돌려가며 목표노드에 도달 가능한지를 확인해야 하는데
실제로는 그렇게 하지 않아도 정답처리가 됩니다.