You are not logged in. Please login at www.codechef.com to post your questions!

×

Error in FREETICKET(INOI14)

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

asked 13 Jan '15, 11:32

nibnalin's gravatar image

6★nibnalin
1611414
accept rate: 0%

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

(20 Jan '15, 15:21) arpanb83★

It is <climits> only. @nibnalin is right

(20 Jan '15, 15:32) sandy9993★

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

(20 Jan '15, 16:05) superty3★

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

(20 Jan '15, 16:08) arpanb83★

Hm, you seem to be correct. Weird...

(20 Jan '15, 16:28) superty3★

It seems that both <climits> and <limits> 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 <limits> and not in <climits>. However you might be wondering how your program still compiles if you change <limits> to <climits>. The answer is that <limits> is also included as part of <algorithm>. If you remove <limits> and <climits> both, your program still compiles. But if you remove <algorithm>, it compiles only with <limits> and not with <climits>.

(20 Jan '15, 16:36) superty3★

Thanks, I learnt something.

(20 Jan '15, 16:37) superty3★

Whoa! Nice!

(20 Jan '15, 16:56) sandy9993★

WOW !!! learnt a lot from this discussion... In Conclusion, Its better to kick out the "climits"...

(20 Jan '15, 17:14) arpanb83★

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

(20 Jan '15, 17:16) arpanb83★
showing 5 of 10 show all

#include <iostream>

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.

link

answered 14 Jan '15, 00:18

Organic-Shilling's gravatar image

0★Organic-Shilling
9318
accept rate: 11%

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!!!

link

answered 17 Jan '15, 19:09

arpanb8's gravatar image

3★arpanb8
120210
accept rate: 13%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×353
×69
×63
×46
×28

question asked: 13 Jan '15, 11:32

question was seen: 804 times

last updated: 20 Jan '15, 17:16