Floyd1 BOJ13141 Ignition BOJ13141 Ignition 그래프가 주어지고, vertex 중 한 개에 불을 질렀을 때 그래프가 모두 타는 최소 시간을 출력 불은 1초에 1만큼 태울 수 있고 어디에 불을 붙여도 그래프가 반드시 전체 다 탈 수 있는 경우만 주어지며 시점과 종점이 같은 edge도 주어지고, 같은 시점과 같은 종점 사이 여러 개의 edge가 존재할 수 있다. 두 가지가 필요하다. 1. 한 vertex에 불이 도달할 수 있는 최소 시간 2. 두 vertex 간 edge가 모두 타는 시간 1의 경우 같은 vertex라도 불을 어디에 붙이느냐에 따라 값이 다르다. 결국엔 all vertex → all vertex의 최단거리를 구해야 하므로 floyd-warshall로 구한다. 2의 경우 두 vertex 간 가장 긴 edge.. 2021. 3. 17. 이전 1 다음
