26125번 - 두 도로
문제 풀이 아이디어가 없어서 한참 헤매다가 겨우 여러 도움받아 풀었습니다.
풀다가 너무 안풀린다 싶으면 보셔요
플로이드 와셜을 돌려서 모든 정점에서 모든 정점으로의 최단거리를 찾음
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개의 시나리오를 직접 구현하면 됨
감사합니다 :)
댓글을 작성하려면 로그인해야 합니다.
k550706 3년 전 2
문제 풀이 아이디어가 없어서 한참 헤매다가 겨우 여러 도움받아 풀었습니다.
풀다가 너무 안풀린다 싶으면 보셔요
플로이드 와셜을 돌려서 모든 정점에서 모든 정점으로의 최단거리를 찾음
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개의 시나리오를 직접 구현하면 됨