n개의 도시가 있고 도시가 두 가지 유형의 도로로 연결되어 있다고 가정합니다. 고속도로와 지름길. 이제 지도가 있고 지도에는 고속도로만 있고 모든 지름길은 없습니다. 도시의 교통부는 고속도로와 지름길을 활용하여 도시를 연결하는 교통수단을 출시하고자 합니다. 우리는 두 도시 사이에 고속도로가 없을 때 두 도시 사이에 지름길이 있다는 것을 알고 있습니다. 여기서 우리의 임무는 시작 도시에서 다른 모든 도시까지의 지름길로 최소 거리를 찾는 것입니다.
따라서 입력이 다음과 같으면
시작 정점(들)이 1이면 출력은 3 1 2가 됩니다.
바로가기만 하면 도시 1과 2 사이의 경로는 1->3->4->2가 되고 비용은 3이 됩니다.
마찬가지로
1 및 3:1->3, 비용 1.
1 및 4:1->3->4, 비용 2.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- graph :=n 세트를 포함하는 새 목록
- 에지의 각 쌍(x, y)에 대해 다음을 수행합니다.
- x :=x - 1
- y :=y - 1
- 그래프[x]에 y 삽입
- 그래프에 x 삽입[y]
- temp_arr :=값 -1을 포함하는 크기 n의 새 배열
- b_set :=키 s - 1을 포함하는 새 지도
- f :=숫자 0에서 n과 b_set 사이의 집합 차이를 포함하는 새 집합
- 색인:=0
- b_set의 크기가 0인 동안 수행
- b_set의 각 요소에 대해 다음을 수행합니다.
- temp_arr[a] :=인덱스
- nxt :=b_set의 하위 집합이 아닌 그래프 값을 포함하는 새 지도
- f :=f와 nxt의 차이 설정
- b_set :=nxt
- 인덱스 :=인덱스 + 1
- b_set의 각 요소에 대해 다음을 수행합니다.
- temp_arr의 0이 아닌 값 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(n, edge, s):graph =[set() for i in range(n)] for (x, y) in edge:x -=1 y -=1 graph[x].add (y) graph[y].add(x) temp_arr =[-1] * n b_set ={s - 1} f =set(range(n)).difference(b_set) index =0 동안 len(b_set)> 0:for a in b_set:temp_arr[a] =index nxt ={f for f in f if not b_set.issubset(graph[f])} f =f.difference(nxt) b_set =nxt index +=1 return( ' '.join(str(t) for t in temp_arr if t> 0)) print(solve(4, [(1, 2), (2, 3), (1, 4)], 1)) 입력
4, [(1, 2), (2, 3), (1, 4)], 1
출력
3 1 2