전체 그래프에서 두 꼭지점 간의 최단 경로

Question

나는 N 개의 꼭지점이있는 완전한 그래프를 가지고 있으며 주어진 소스에서 주어진 대상까지의 최단 경로를 찾아야합니다. 모든 에지는 초기 비용 A를 가지고, K 에지의 경우 비용은 B로 바뀔 것입니다. 꼭지점 1과 꼭지점 N 사이의 최소 비용을 찾는 가장 좋은 방법은 무엇입니까? [알고리즘은 꼭짓점 1 사이의 최단 경로 (즉, 최단 경로)를 찾습니다. 및 꼭지점 N]? 입력은 N K A B 및 K 에지 (비용 B를 갖는 에지)입니다.

2 <= N <= 500000 
0 <= K <= 500000 
1 <= A, B <= 500000 

내가 다 익스트라으로 시도했지만 ~ 많은 시간에 2 분을, 내가 2 초 같은 뭔가가 필요 :

.

Answer 1

1. 는 1 및 N 사이의 에지의 비용 A 경우.

   1) A<B 인 경우 최저 비용은 A입니다.

   2) A>B 있다면, 비용 B 만 가장자리를 통해 N에 1에서 가장 적은 홉을 찾을 수 BFS를 사용합니다. 예를 들어 L 사이의 가장자리가 1과 N 사이에 있다고 가정하면 min(LB,A)을 반환하십시오. 전형적으로 BFS이고 비용은 O(N+K)입니다.

2. 1과 N 사이의 가장자리가 B 인 경우.

   1) 'A> B'이면 대답은 B입니다.

   2) 에서 N까지 가장 작은 홉을 찾으려면 비용이 A 인 엣지 만 사용하십시오. S[h]은 h 홉으로 도달 할 수있는 버텍스 집합이되고 S'은 아직 도달하지 않았 으면 다음과 같이 해결할 수 있습니다.

   min_dis() { S[0] = {1}; int h = 0; S'={2,...,N}; while (S[h] is not empty) { S[h+1] = {}; for_each (v1 in S'){ for (v2 in S[h]) { if (cost[v1][v2] == A) { S[h+1].insert(1); S'.remove(v1); if (v1 == N) return min((h+1)*A, B); break; } } } h++; } return B; }

   우리가 할 수있는이 알고리즘은 각 시간 이후 우리는 const[v1][v2]==A가, S'의 크기가 1 감소됩니다 true입니다 테스트하고이 테스트 false 때문에 경우 대부분에서 K 시간이있다, 또한 O(N+K) 것을 증명 비용이 B 인 최대 K 가장자리가 있습니다. 그래서 총에 O(N+K)

완료 될 보장, 알고리즘은 2sec 시간 제한을 보장합니다 O(N+K)입니다.