Floyd-Warshall實現中的錯誤是什麼？

這是問題鏈接：http://codeforces.com/contest/295/problem/B Floyd-Warshall實現中的錯誤是什麼？

Greg有一個加權有向圖，由n個頂點組成。在這個圖中，任何一對不同的頂點在兩個方向上都有一條邊。 Greg喜歡玩這張圖，現在他發明了一款新遊戲：

遊戲包含n個步驟。在第i步Greg從圖中移除頂點數xi。當Greg刪除一個頂點時，他還刪除了進出該頂點的所有邊。在執行每一步之前，Greg希望知道所有其餘頂點對之間最短路徑的長度總和。最短路徑可以穿過任何剩餘的頂點。幫助Greg，在每一步之前打印所需金額的值。

輸入：

第一行包含整數n（1≤N≤500） - 在圖形的頂點數目。

接下來的n行包含n個整數 - 圖鄰接矩陣：第i行aij中的第j個數（1≤aij≤105，aii = 0）表示從頂點開始的邊的權重我到頂點j。

下一行包含n個不同的整數：x1，x2，...，xn（1≤xi≤n） - Greg刪除的頂點。

輸出：

打印n個整數 - 第i個數量等於第i個步驟之前所需的總和。因此，基本上我的方法是在刪除任何頂點之前運行Floyd-Warshall算法，並且爲了刪除，我將簡單地將鄰接矩陣中要刪除的頂點的值設置爲INT_MAX。

基本上，這個循環是main

for (int h = 0; h < n; h++) 
    { 
     func(); 
     int val = arr[h]; // arr contains the vertices to be deleted 
     for (i = 1; i <= n; i++) 
      dist[val][i] = INT_MAX; 
     for (i = 1; i <= n; i++) 
      dist[i][val] = INT_MAX; 
    }

這是我實現Flloyd沃肖爾算法：

void func() 
{ 
    //int i,j,k; 
    ans = 0; 
    for (i = 1; i <= n; i++) 
    { 
     for (j = 1; j <= n; j++) 
     { 
      if (i == j) 
       val[i][j][0] = 0; 
      else if (dist[i][j] != 0) 
       val[i][j][0] = dist[i][j]; 
      else 
       val[i][j][0] = INT_MAX; 
     } 
    } 
    for (k = 1; k <= n; k++) 
     for (i = 1; i <= n; i++) 
      for (j = 1; j <= n; j++) 
       val[i][j][k] = min(val[i][j][k-1],val[i][k][k-1]+val[k][j][k-1]); 
    //int ans = 0; 
    for (i = 1; i <= n; i++) 
     for (j = 1; j <= n; j++) 
      ans = ans + val[i][j][n]; 
    cout<<ans<<"\t"; 
}

這裏，val是，我做了全球3 d矩陣， arr包含要刪除的頂點。然而，當我運行這個邏輯時，它只在最初纔給出正確的答案，即沒有頂點被刪除。但在此之後，它給出了錯誤的價值。我不明白爲什麼？我的邏輯不正確？

來源

2015-09-15 rohansingh

做一個很小的圖，移除一個頂點並**調試**你的代碼。找到自己的錯誤比我們爲你做的更好（假設我們可以找到它）。 – Manu

一兩件事，看起來很奇怪的是，在你到底是爲了計算所有對剩餘頂點的總和，但你的循環是簡單地在所有的頂點：

for (i = 1; i <= n; i++) 
    for (j = 1; j <= n; j++) 
     ans = ans + val[i][j][n];

來源

2015-09-15 11:51:11

Floyd-Warshall實現中的錯誤是什麼？

回答

相關問題