[일반] 오늘 ABC D 어케 푸는거임?

[익명(218.48)]

다리 돌아가는거 짧은 방향 쪽으로 가고, 잘라진 다리만큼 사이클 생기는거 더하는 거로 접근했는데 이걸 어떻게 줄일지 모르겠음

[익명(222.109)]

a에서 b로 가는 경로 두 개중에 짧은 부분을 A, 긴 부분을 B, 이 두 경로의 거리 차를 d라 하면 B 부분의 다리가 잘리는건 영향을 주지 않고, A 부분의 다리가 잘리면 B 부분으로 돌아가야 하기 때문에 d만큼 전체 경로가 늘어남 즉, A부분에 포함된 다리가 잘리면 전체 경로가 d만큼 늘어난다고 볼 수 있으니까 A부분에 포함된 다리 각각에 d만큼 더해주는 식으로 모든 경로에 대해서 해준 다음에 가장 적게 늘어나는 다리 잘라주면 돼

[익명(1.239)]

각 다리별로 그 다리를 이용하는 모든 경로의 길이를 구하면, n*경로갯수-최단경로로 다리별로 뒤집어줄 수 있음

[익명(223.62)]

걍 세그써서 밈

[익명(14.49)]

나도 걍 레이지 세그 씀