Floyd-Warshall 算法实现的问题

Question

我试图解决 INOI 2014 paper 中的第二个问题，即。 FREETICKET 并使用 Floyd-Warshall 算法计算答案。我的代码似乎在最后一个子任务中失败，并且似乎为 WA 提供了一对测试 cases.The 代码如下：

#include <iostream>
#include <cstdio>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;

typedef vector<long long int> vl;
typedef vector<vl> vvl;

long long int maxelem(const vvl& arr)
{
     long long int max = 0, curmax;
     for(int i = 0, l = int(arr.size());i < l;i++)
     {
             curmax = *(max_element(arr[i].begin(), arr[i].end()));
             if(curmax > max)
             {
                  max = curmax;
             }
     }
     return max;
}

int main(void)
{
    long long int c, f, x, y, p;
    scanf("%lld%lld", &c, &f);
    vvl adj(c, vl(c, 26336));
    for(int i = 0;i < f;i++)
    {
         scanf("%lld%lld%lld", &x, &y, &p);
         adj[x-1][y-1] = p;
         adj[y-1][x-1] = p;           
    }
    long long int max = 0;
    for(int k = 0;k < c;k++)
    { 
            for(int i = 0;i < c;i++)
            {
                    for(int j = 0;j < i;j++)
                    {
                            adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);        
                    }
                    for(int j = (i + 1);j < c;j++)
                    {
                           adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);         
                    }      
            }
    }
    max = maxelem(adj);
    printf("%lld\n", max);
}

此代码仅使用邻接矩阵并确保此人不会尝试从同一个地方去同一个地方（在最内层循环中）。它未能解决子任务 3 中的一些子任务，并给我 50/100 分。谁能帮我找出代码中的错误？我什至尝试将数据类型更改为 long long int 的。（为了安全起见）。

Answer 1

你的算法的问题是：

for(int i = 0;i < f;i++)
{
      scanf("%lld%lld%lld", &x, &y, &p);
      adj[x-1][y-1] = p;
      adj[y-1][x-1] = p;           
}

应该是：

 for(int i = 0;i < f;i++)
 {
      scanf("%lld%lld%lld", &x, &y, &p);
      adj[x-1][y-1] = min(p, adj[x-1][y-1]);
      adj[y-1][x-1] = min(p, adj[y-1][x-1]);           
 }

因为如果城市a->b之间有多条路线，我们只需要走最便宜的路线即可。

并且您还需要为所有 0 <= i < c

设置每个 adj[i][i] = 0

Floyd-Warshall 算法实现的问题

Problems with Floyd-Warshall algorithm implementation

c++

algorithm

debugging