c++ - Floyd-Warshall 算法实现的问题

Question

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

#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之间有多条路线，我们只需要走最便宜的路线即可。

而且你还需要设置每个adj[i][i] = 0对于所有 0 <= i < c