정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. 이때, 특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것이다. 연결이란 두 정점이 간선을 통해 방문 가능한 것을 말한다.
s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가하는 간선의 순서를 조정할 때, 그 최솟값을 구하시오.
jos6151 2년 전 3
정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. 이때, 특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것이다. 연결이란 두 정점이 간선을 통해 방문 가능한 것을 말한다.
s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가하는 간선의 순서를 조정할 때, 그 최솟값을 구하시오.
위의 지문에서 s와 t가 연결되는 시점에서 간선 추가를 멈춘다는 지문 때문에
위의 예제에서
5 정점과 8 정점이 연결되는 순간 멈춰서 다익스트라를 체크하면 11이 됩니다.
근데 이건 아니구요
"s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가하는 간선의 순서를 조정할 때" 라는 지문이 있어요.
즉 최대한 가중치가 낮은 상태로 연결시켜버리는 상태를 상정해서 간선 추가 순서를 조정할 수 있다는 거니
다 추가해서 다익스트라 돌리면 됩니다. 시간이나 메모리가 그 정도로는 초과가 되지는 않더라구요.
요약하자면 순서대로 추가되는 상황에서 s와 t가 연결되는 그 순간 다익스트라 돌리는 것이 아니라 가중치가 최소한이 되는 상태로 연결된 상황을 가정할 수 있도록 간선 추가 순서를 조정한 상태에서의 가중치를 구하는 것입니다.