플로이드 최단거리 뭔소린지 모르겠다.. 도움좀

[익명(175.213)]

짤 최단거리구하는데 뜬금없이 E에서 A를 거쳐서 B, C로 가는 거리랑 E에서 B, C로 가는 거리를 비교하는데
E가 대체 왜 나오는거임??

[0xrgb(0xrgb)]

예시임

[익명(175.213)]

ㄴ ㄴㄴ A0에서 바로 E나와서 비교함

[0xrgb(0xrgb)]

그러니까 floyd가 이제 A부터 E까지를 하나씩 중간지점으로 두면서 거리를 줄여나갈거란 말이지

[0xrgb(0xrgb)]

예를들어서 A가 중간지점이면 a -> A -> b가 a->b의 현재 거리 보다 짧으면 갱신하는형태임

[익명(175.213)]

ㄴ 아하 ㄱㅅㄱㅅ

[0xrgb(0xrgb)]

그런데 보면 알겠지만 다른데는 A타고 갱신할곳이 없음. E에서 나가는 것만 갱신이 보임

[0xrgb(0xrgb)]

그리고 이번에 B를 중간지점으로 잡으면 또 몇몇구간이 갱신되겠지? 이걸 다 해주면 되는거임

[익명(175.213)]

어렵누

[0xrgb(0xrgb)]

덤으로 PS 마갤좀!

[익명(175.213)]

넹ㅋㅋ

[ㅁㅈㅇㅇ(49.170)]

백준 평소에 꾸준히 푼 사람들은 쉽게 이해한당~ 그냥 3중 dp임 솔직히 플로이드 새끼 아니어도 저정도 생각할만한 학부생 대한민국에도 많을듯