在線評測PS [Floyd_Warshal，C++]

我解決這個問題 https://www.acmicpc.net/problem/1238#在線評測PS [Floyd_Warshal，C++]

您可以通過點擊按鈕來更改語言

我想出了這個想法是找到的總和從第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（）函數沒問題。

但是，我想我採取了一個錯誤的方法（上述建議）來解決問題，所以我只想問，我的想法是正確的方法來解決問題或不。

來源

2017-02-27 logan shin

你可以發佈問題陳述的快速摘要嗎？我沒有看到翻譯按鈕，Google翻譯也沒有提供足夠清晰的內容給我。 – IVlad

因爲這個問題被定義爲'C'，所以'C++'語句在代碼中做了什麼：'using namespace std;'這會導致c編譯器產生一個ERROR消息。 – user3629249

發佈的代碼不能編譯。這是因爲它包含（按標籤）C代碼中的C++語句。 – user3629249

的所述Floyd-Warshall算法的複雜度是爲O（n 3 ）。它會是TL。

該任務的解決方案是做SSSP（單一來源最短路徑）。它可以有效地用Dijkstra的算法。您可以在農場X上執行Dijkstra的算法，然後再次使用相反的邊進行操作。它具有O（m logn）複雜性，如果您使用優先級隊列或集合編寫它。谷歌爲此，有許多信息，例如1,2。

之後，您的想法是正確的，你應該爲每個農場i最大總和D[i][X] + D[i][X]。儘管你已經寫了2而不是x，但它可能是一個錯字或測試代碼。

來源

2017-02-27 20:58:52

在線評測PS [Floyd_Warshal，C++]

回答

相關問題