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
I realize this is a tedious work but please help me, it’s really important.
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;
}
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.
@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 ~.~ )
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.
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 ~.~ )