k550706   3년 전

문제 풀이 아이디어가 없어서 한참 헤매다가 겨우 여러 도움받아 풀었습니다.

풀다가 너무 안풀린다 싶으면 보셔요


플로이드 와셜을 돌려서 모든 정점에서 모든 정점으로의 최단거리를 찾음

N개의 줄에 각각 두 도로의 데이터가 (a,b,c),(d,e,f)로 주어짐

편의상 (a,b,c)는 도로1 / (d,e,f)는 도로2라고 명명함

현재 플로이드 와셜의 2차원 배열을 g라고 하고 시작점에서 끝점까지의 데이터가 g[s][t]라고 한다면

두 도로가 만들어졌을 시나리오에서 g[s][t]가 더 줄어들 시나리오는 총 4개임

1.s에서 t로 가는 최단거리가 s -> 도로1 -> t로 줄어들 경우

2.s에서 t로 가는 최단거리가 s -> 도로2 -> t로 줄어들 경우

3.s에서 t로 가는 최단거리가 s -> 도로1 -> 도로2 -> t로 줄어들 경우

4.s에서 t로 가는 최단거리가 s -> 도로2 -> 도로1 -> t로 줄어들 경우

1번을 예시로 보면

g[s][a] + c + g[b][t]가 g[s][t]보다 작아질 경우에 g[s][t]가 더 줄어듬

이를 잘 이해해보면 s에서 시작하여 도로1 시작점인 a까지 간다음에

c의 비용을 써서 도로1 마지막점인 b까지 가고 거기서 t까지 가는 비용임

이와 같이 총 4개의 시나리오를 직접 구현하면 됨

741u741   1년 전

감사합니다 :)

댓글을 작성하려면 로그인해야 합니다.