Hi!
Firstly, I hope you understand the motivation behind Dijkstra’s algorithm. It’s good to look through the proof (so you know why negative edges can’t be handled), but just a understanding behind the motivation is enough for tackling simple problems. Imagine you put some water at the first node, and let it flow. Each edge’s cost is represented by its length. Now, at each iteration of the main loop in Dijkstra’s algorithm, you mark the node which the water would touch next. Try drawing this on a whiteboard or piece of paper, visualizing the water flowing through.
Secondly, in plaintext, the solution of the “freeticket” problem is as follows—for each node, you find the farthest node that can be reached by starting from it. For all such “farthest nodes”, you take the most costly one. It is like putting water in each node, one at a time, and marking the node where it reaches last. You do this for every node, and then take a maximum over all such values.
int max_flight = INT_MIN;
for (i = 0; i < C; i++) {
max_flight = max(max_flight, run_dijkstra_algorithm(i /* start node*/*));
Where run_dijkstra_algorithm returns the cost of the cheapest flight to the “farthest node”.
Here’s a simple solution in C, which I’ve hacked together with comments so the syntax isn’t an issue:
// flights[i][j] is the cost of the flight from i to j. -1 means no such flight.
// For each node from 0 to C - 1, you make this the "first node".
for (i = 0; i < C; i++) {
long long distance[C]; int visited[C];
// This is the inner loop, basically the Dijkstra's algorithm.
// visited[i] is set to 1 if water has "reached" the node, else 0.
// distance[i] marks the current cheapest distance to a node.
// From i, by just taking one flight, you mark the cost to reach each node. Water hasn't
// yet reached any node, except i (because you started from it).
for (j = 0; j < C; j++)
distance[j] = flights[i][j], visited[j] = 0;
visited[i] = 1;
while (1) {
// Now you find the next node that water would reach.
// This translates to the next minimum value of distance[i].
int min_flight = -1, min_distance = INT_MAX;
for (j = 0; j < C; j++)
if (distance[j] != -1 && !visited[j]
&& distance[j] < min_distance) {
min_distance = distance[j];
min_flight = j;
}
// If you've reached all nodes you could, then you've visited
// the "farthest node". Now go start from another node.
if (min_flight == -1)
break;
visited[min_flight] = 1;
// Is this the costliest flight trip you've taken yet? Mark it!
if (min_distance > max_cost) max_cost = min_distance;
// Now this is some updating time of the distance array.
// How this works is simple. If, from the newly visited node, you can visit
// some other node cheaper, or some other node you couldn't visit before,
// you mark it so.
for (j = 0; j < C; j++) {
if (flights[min_flight][j] != -1) {
if (distance[j] == -1 ||
distance[j] > min_distance + flights[min_flight][j]) {
distance[j] = min_distance + flights[min_flight][j];
}
}
}
}
}
Lastly, your code. I didn’t take a deep look, but if I’m not wrong, for each node, you’re just marking the maximum “first flight” it could take.
EDIT: Oops. Forgot some motivation jumbo mumbo. If everyone solved all problems in their first go, surely they’d be no need for competitions to motivate us to learn more? It’s okay. You’ll soon solve one. Then another. Then all. What’s important is to enjoy the process, to struggle through the problem while you can—and most importantly, to know when’s the right time to give up and ask on CodeChef! 
Hope I could help,
Cheers.
