플로이드 알고리즘의 구조가 k번째 루프에 정점 0~k번을 사용해 갈 수 있는 최단거리를 갱신하는데,

이 문제에서는 최단거리에다가 이 경로를 거치는 정점들 중 가장 큰 패널티값까지 더해야 하고 그 결과들 중 가장 작은 걸 찾아야 합니다.

때문에 경로 중에서 가장 큰 패널티값이 문제인데,

k번째로 패널티가 작은 정점을 사용해서 최단거리 및 W 배열을 갱신하면 W[i][j]를 w를 우회하는 경로로 갱신할 때 max(delay[i],max(delay[j],delay[w])) 구문처럼 i, j, w의 패널티 정보만 가지고도 갱신할 수 있게 됩니다.

왜냐면 i, j, w 정점의 패널티 중 최댓값만 보아도, 이 경로상에서 가장 큰 패널티값을 알 수 있기 때문입니다.

지금까지는 w보다도 패널티가 적은 정점들만을 사용해서 최단거리를 갱신해 왔으므로, 만약 이번에 w를 추가로 지나서 새로운 최단 경로를 갱신한다면 그 경로상의 정점들 중 가장 패널티가 큰 정점이 w일 것이기 때문이죠.