hjhj97

[CF 1076D] Edge Deletion - 1800 문제 설명 : 풀이 : 다익스트라 알고리즘의 원리를 얼마나 잘 알고있는지를 물어보는 문제이다. 다익스트라 알고리즘을 돌면서 매 번 dist[]값이 가장 작은 노드를 찾아가서 그 노드에서 갈 수 있는 edge들을 갱신하는 반복을 작업하게 된다. 이때 중요한 성질은, 다익스트라에서 한 번 방문한 노드는 방문한 순간 dist[]값이 최소라는게 보장된다(여기서 말하는 '방문'이란 min heap의 top에 있는 노드로써 말하는 것이다). 따라서 이 문제에서 최대 k개의 edge를 남겨서 최단경로가 여전히 존재하는 노드의 개수를 최대한 많이 남기라는 것은 다익스트라를 돌리면서 방문하게 되는 k개의 노드를 저장하면 되는 것이다. 그리고 본인이 어떤 edge를..