オンライン判事PSは、[Floyd_Warshalは、C++は]

Question

は、私は私が思いついたアイデアはある

は、の合計を見つけるために、あなたはボタンをクリックして言語を変更することができます https://www.acmicpc.net/problem/1238#

この問題を解決しています第二ので、ここでK番目

に2番目の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（単一ソースの最短パス）です。それはダイクストラのアルゴリズムで効果的に行うことができます。ファームXでDijkstraのアルゴリズムを実行し、エッジを逆にしてもう一度やり直すことができます。プライオリティキューを設定したり、設定したりすると、複雑さが増します（O（m logn））。 Googleには、多くの情報があります（例：1、2）。

この考え方が正しい場合は、ファームごとに合計D[i][X] + D[i][X]を入力してください。ixの代わりに2と書いてありますが、おそらくタイプミスであるか、テストコードです。