Error in FREETICKET(INOI14)

general
, , , ,
1

I tried solving the FREETICKET problem from INOI 2014 using floyd-warshall algorithm. Following is the code I wrote:

#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 no one tries 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 ?

Thanks!
nibnalin

2

#include 

using namespace std;

int C, F;
long long int maxx = 1000000000000000; //effectively infinite

int main()
{
 ios::sync_with_stdio(0);
 cin >> C >> F;
 
 long long int costs[C][C];
 
 for(int i = 0; i < C; i++){
 for(int j = 0; j < C; j++){
	if(i == j)
	costs[i][i] = 0;
    else
	costs[i][j] = maxx;
 }
 }
 
 for(int i = 0; i < F; i++){
	int a, b, c;
	cin >> a >> b >> c;
	costs[a - 1][b - 1] = costs[b - 1][a - 1] = c;
}

long long int maximum = 0;

for(int k = 0; k < C; k++){
for(int i = 0; i < C; i++){
for(int j = 0; j < C; j++){
	costs[i][j] = min(costs[i][j], costs[i][k] + costs[k][j]);
}
}
}		

for(int i = 0; i < C; i++){
for(int j = 0; j < C; j++){
if(maxx != costs[i][j])
maximum = max(maximum, costs[i][j]);
}}

cout << maximum << '\n';

}

Our codes seem to be extremely similar. You could download the test data and run the code on both and compare the memory states.

3

There are slight mistakes in the implementation of the algorithm. Check out my Floyd-Warshall solution (Thanks to @sandy999 for debugging and correcting my code). Here it is: cpp.sh/6qpy

HOPE THIS HELPS!!!

4

I guess the header file is and not /<limits.h>…not very sure…Its probably a C++ header file (not from the C lib)

5

It is only. @nibnalin is right

6

You wouldn’t even be able to compile the code if it was the wrong header file, let alone get 50/100.

7

No, both & work…I checked out…Here’s my soln. to Calvins Game…I used and it got a 100…http://cpp.sh/6np

8

Hm, you seem to be correct. Weird…

9

It seems that both and exist but they are entirely different header files having different members.
http://www.cplusplus.com/reference/climits/
http://www.cplusplus.com/reference/limits/

numeric_limits is defined only in and not in .
However you might be wondering how your program still compiles if you change to . The answer is that is also included as part of . If you remove and both, your program still compiles. But if you remove , it compiles only with and not with .

10

Thanks, I learnt something.

11

Whoa! Nice!

12

WOW !!! learnt a lot from this discussion…
In Conclusion, Its better to kick out the “climits”…

13

@superty I also verified it from the same source cplusplus.com … it was nice of u 2 provide the link