온라인 판사 PS는 [Floyd_Warshal는, C는 ++]

Question

는 내가 생각 해낸 아이디어는

이의 합을 찾기 위해 당신은 버튼을 클릭하여 언어를 변경할 수 있습니다 https://www.acmicpc.net/problem/1238#

이 문제를 해결하고 두 번째와 그래서 여기에 K 번째

두 번째로 K 번째에서 최단 거리 내 전체 소스 코드

#include <stdio.h> 
#define INF 999999 
#define min(x,y) ((x)>(y)?(y):(x)) 
using namespace std; 

int ans = 0; 
int n,m,x; 
int d[1001][1001]; 

void Floyd_Warshal(){ 
    for(int i=1; i<=n; i++){ 
     for(int j=1; j<=n; j++){ 
      if(i==j) d[i][j]=0; 
     } 
    } 
    for(int k=1; k<=n; k++){ 
     for(int i=1; i<=n; i++){ 
      for(int j=1; j<=n; j++){ 
       d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
      } 
     } 
    } 
} 

void solve(){ 
    for(int i=1; i<=n; i++){ 
     if(i==2) continue; 
     if(d[i][2] + d[2][i]>ans) ans = d[i][2] + d[2][i]; 
     //printf("%d = %d+%d \n",ans,d[i][2],d[2][i]); 
    } 
} 

int main(){ 
    scanf("%d %d %d",&n,&m,&x); 
    for(int i=1; i<=n; i++){ 
     for(int j=1; j<=n; j++) d[i][j] = INF; 
    } 
    for(int i=0; i<m; i++){ 
     int u,v,t; 
     scanf("%d %d %d",&u,&v,&t); 
     d[u][v] = t; 
    } 
    Floyd_Warshal(); 
    solve(); 
    printf("%d\n",ans); 
    return 0; 
} 

Floyd_warshal() 함수는 괜찮다고 생각합니다.

하지만 문제를 해결하기 위해 잘못된 접근 방식 (위의 제안 사항)을 취하여 문제를 해결하기위한 올바른 접근 방식인지 묻고 싶습니다.

Answer 1

플로이드 - 워셜 알고리즘의 복잡성 O (N ³)이다. 그것은 TL이 될 것입니다.

이 작업의 해결책은 SSSP (단일 소스 최단 경로)입니다. 그것은 Dijkstra의 알고리즘으로 효과적으로 할 수 있습니다. 팜 X에서 Dijkstra 's Algorithm을 수행 한 다음 가장자리를 반대로 다시 수행 할 수 있습니다. 우선 순위 대기열을 사용하여 쓰거나 설정하면 O (m logn) 복잡합니다. 이를 위해 Google에는 많은 정보가 있습니다 (예 : 1, 2).

생각이 옳은 후에는 각 팜에 최대 D[i][X] + D[i][X]을 가져 가야합니다. i. x 대신 2을 작성했으나 오타이거나 코드를 테스트 한 것일 수 있습니다.