CODEWITHSUNDEEP
c++algorithmdebugging
Nalin Bhardwaj
Nalin Bhardwaj

Reputation: 223

Problems with Floyd-Warshall algorithm implementation

I was trying to sole the second problem from the INOI 2014 paper ie. FREETICKET and used Floyd-Warshall algorithm to compute the answer. My code appears to fail in the final subtask and appears to give WA for a couple test cases.The code follows:

#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);
}

This code just uses an adjacency matrix and ensures that the guy doesn't try to go from the same place, to the same place(in the innermost loop). It fails to solve some of the subtasks from subtask 3 and yields me 50/100 marks. Can anyone help me finding the bug in my code ? I have even tried changing the data type to long long int's.(Just to be safe).

Upvotes: 1

Views: 169

Answers (1)

Pham Trung
Pham Trung

Reputation: 11294

The problem for your algo is:

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;           
}

It should be:

 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]);           
 }

Because, if there are multiple routes between city a -> b, we just need to take the cheapest route.

And you also need to set each adj[i][i] = 0 for all 0 <= i < c

Upvotes: 2

Related Questions