×

# Error in FREETICKET(INOI14)

 0 I tried solving the FREETICKET problem from INOI 2014 using floyd-warshall algorithm. Following is the code I wrote: #include #include #include #include #include using namespace std; typedef vector vl; typedef vector 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 6★nibnalin 161●1●5●16 accept rate: 0% I guess the header file is and not /...not very sure...Its probably a C++ header file (not from the C lib) (20 Jan '15, 15:21) arpanb83★ It is only. @nibnalin is right (20 Jan '15, 15:32) sandy9992★ 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 & work...I checked out...Here's my soln. to Calvins Game...I used 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 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 . (20 Jan '15, 16:36) superty3★ Thanks, I learnt something. (20 Jan '15, 16:37) superty3★ Whoa! Nice! (20 Jan '15, 16:56) sandy9992★ 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

 0 #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. answered 14 Jan '15, 00:18 93●1●1●8 accept rate: 11%
 0 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!!! answered 17 Jan '15, 19:09 3★arpanb8 120●1●3●12 accept rate: 13%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×385
×69
×65
×51
×31

question asked: 13 Jan '15, 11:32

question was seen: 865 times

last updated: 20 Jan '15, 17:16