# Can someone solve FREETICKET from INOI 2014?

Hi everyone.
I’ve been practicing on the INOI server lately, however I’ve not yet solved even a single question. I studied Graph Theory for the first time last week and decided to do the FREETICKET problem using Djikstra’s Algorithm ([here][1]).

I’ve tried to solve the problem innumerable times, but am still not able to do so. If someone could please tell me the pseudocode, it’ll be of great help. I’m asking for the pseudo code as I program in Java and am sometimes not able to understand c++ syntax.

Also, if you could review my pseudo code once, I’ll be very grateful.

``````

int[] max = new int[vertices]
for each vertex u = 1 -> v:
int[] dist = new int[vertices]
dist[u] = 0
for each int i = 1 -> v:
if i != u:
dist[i] = INFINITY
for each int i = 0 -> v:
if edge exists from u->i:
int tmp = dist[u] + weight[u][i]
if tmp < dist[i]:
dist[i] = tmp
max[u] = maximum(dist)
int f = maximum(max)
return f            //here max is an array and maximum is the
//function for finding maximum value

``````

Thank you all for your help, guys.

Note: when I’m trying the sample case, it returns maximum int value, which means the relaxation is not being done properly.
[1]: http://www.iarcs.org.in/inoi/2014/inoi2014/inoi2014-qpaper.pdf

1 Like

First of all, you didn’t link to the problem statement, I hope it’s this - http://www.iarcs.org.in/inoi/2014/inoi2014/inoi2014-qpaper.pdf

Does you code work for relabeled graph (1->3, 2->4, 3->1, 4->2 = every vertex +2, so longest is still 1->4, relabeled 3->2)

``````4 5
3 4 10
3 1 24
4 1 2
4 2 15
1 2 7
``````

(please validate whether I made no mistake in relabeling in input first)

In this problem, we need to know the minimum cost to travel between all pairs of cities.

In an all pairs shortest path problem, the Floyd Warshal algorithm is faster and a lot simpler to code. You have the algorithm description and pseudo-code in the wikipedia link.

I gave INOI 2014 last year and I also implemented iterative Dijsktra’s. I got only 20/100
Dijkstra’s Algo won’t pass. Since it asks maximum of minimum paths then why don’t you use Floyd Warshal algorithm? I got 100/100 using this on the IARCS grader. Here is my code:

``````int main() {
int c,f;
cin >> c >> f;
int graph[c][c];
for(int i = 0;i < c;i++)
for(int j = 0;j < c;j++)
graph[i][j] = 100000007;
for(int i = 0;i < c;i++)
graph[i][i] = 0;
int x,y,p;
for(int i = 0;i < f;i++) {
cin >> x >> y >> p;
graph[x-1][y-1] = p;
graph[y-1][x-1] = p;
}
int dist[c][c], i, j, k;
for(i = 0; i < c; i++)
for (j = 0; j < c; j++)
dist[i][j] = graph[i][j];
for(k = 0; k < c; k++) {
for(i = 0; i < c; i++) {
for(j = 0; j < c; j++) {
if(dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
int ans = 0;
for(int i = 0;i < c;i++)
for(int j = 0;j < c;j++)
ans = max(ans,dist[i][j]);
cout << ans << endl;
return 0;
}``````
4 Likes

I tried a Dijkstra over every single edge, and got a 100/100.
Just remember to use a min-heap instead of a priority queue for implementing Dijkstra. It’s a lot faster.

Here’s the link to the code:
FREETICKET

Since you are asking for Pseudocode, this code is pretty easy to understand. Still if you have any problem, fell free to ask (:

1 Like

@ketanhwr Bro, thanks a lot for your great help. Actually, I’d used Floyd-warshall but somehow, my implementation was messing up. After looking at your code, I realized how simple the thing was and how I was just over complicating it. Thanks once again Also, much did you score in INOI last year? (if you don’t mind, can you tell me your class too? I hope you’re not in class 10th or younger ~.~ )

2 Likes

I’m in 12th right now. And I have been qualifying for INOI since 10th. I got 40/200 last year

Hey @ketanhwr Nice and simple code, but why doesn’t it seem to work when I substitute 100000007 with INT_MAX? It doesn’t even work for the sample test case when I do that! Without the INT_MAX, it works fine though.