k550706   4년 전

문제는 아래와 같습니다.

정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. 이때, 특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것이다. 연결이란 두 정점이 간선을 통해 방문 가능한 것을 말한다.

s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가하는 간선의 순서를 조정할 때, 그 최솟값을 구하시오.


예제의 경우

8번과 최초로 연결되는 구간을 살펴보면(특정 정점 s와 t가 연결되는 시점)

아래 소스코드상에서 8번라인(5번노드 -> 8번노드)이 입력되었을떄이고


이때의 최소 가중치의 합은

1->2->5->8로 움직였을때이므로

3+2+6=11입니다

근데 예제의 답은 5로 되어있습니다

내용을 읽어봤을땐 하나의 간선을 추가할때마다 데이크스트라를 돌려야 하는거 같은데,

혹시나해서 답을 제출해보니 단순 데이크스트라를 돌리면 정답으로 처리 되어있습니다.

문제를 읽어보면 간선 m개가 있는데, 이 중에 하나씩 추가를 하면서

그때마다 데이크스트라를 돌려가며 목표노드에 도달 가능한지를 확인해야 하는데

실제로는 그렇게 하지 않아도 정답처리가 됩니다.

pill27211   4년 전

하나의 간선을 추가할때마다 다익스트라를 돌리는 게 아니라, 그냥 한 번만 해도 되는 거 아닌가요 ?

예제의 답은

1 -> 3  (비용 2)

3 -> 6 (비용 1)

6 -> 8 (비용 2)

로 5가 맞네요.

k550706   4년 전

8번 정점과 연결된 시점은 8번째 라인이므로

9번 라인인 6 -> 8 간선은 이용불가합니다.

(문제에 제시된 대로 특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것)

wnwoghd22   4년 전

좀 헷갈리긴 하지만, 문제를 잘 읽어보면

입력된 순서대로 간선을 추가하는 게 아니라

최단 거리가 되도록 임의로 추가하는 순서를 바꿀 수 있다고 되어있습니다.

그냥 최단 거리를 구하면 그게 정답이라는 얘기를 왜 이리 어렵게 써놨을까요;;

k550706   4년 전

아..

s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가하는 간선의 순서를 조정할 때, 그 최솟값을 구하시오.

라고 써있는거 때문에

간선을 추가하지 않는다는게 전혀 의미없는 이야기가 되었군요

감사합니다

댓글을 작성하려면 로그인해야 합니다.