I proposed a problem called “Problem C – Omar the Bus Driver” which was on Scorify platform, and I would like to share its solution in this post. I am not that happy about it because the problem statement was ambiguous, and some cases were not consistent even if they will not change the output. I checked this point after the requests in clarifications because some contestants used *assert *to check it.

The case that was not consistent was :

**3** 1 8

**3** 0 0

So the number of nodes is 3 and the only edge connects a node with index 3 and a node with index 0 which is *NOT* consistent to the problem statement. And I am sorry about it.

And the hero was my friend *Omar Salim Moussa*. So, this problem was a gift for him.

## I am sorry 😦

I apologize for all the contestants who tried this problem and find it ambiguous. I know some contestants spent a lot of time trying to solve it. I deeply apologize specifically to *Pythonista, Pinky and the Brain, Koding4Khobz *teams. The problem can be seen for the first time as traveling salesman problem. I hope I corrected this ambiguity in the clarifications. And I hope it did not affect the overall standing. I took it very seriously, but these things happen. And I am really sorry about it. I hope it will not be repeated next time. It is the first time I write a problem for a contest, but I am not taking it as an excuse.

## Problem Statement:

Omar is a bus driver in a famous traveling Moroccan company. Omar travels once per day, and he visits daily N cities. He has a serious problem because he does not know if the initial volume of Gasoline is enough to visit the N cities. Your task is to help Omar to know if he can traverse all the N cities with the minimum cost so that he can know if the initial volume of gasoline is enough to do so.

Input:

The input consists of several test cases. Each test case starts with a line with three non-negative integers, 1 ≤ N ≤ 20000, and 0 ≤ M ≤ 30000, and 1 ≤ G ≤ 30000, separated by a single space, where N is the numbers of cities and M is the number of roads, and G the initial volume of Gasoline. Cities are numbered from 0 to N−1. Then follow M lines, each line consisting of three (space-separated) integers u, v and g indicating that there is a road between u and v such that if the bus traverses this road, it will consume g liters of Gasoline where 0 ≤ g ≤ 20000. Roads are undirected.

Input will be terminated by a line containing -1 -1 -1, this line should not be processed.

Output:

For every test case, if there is no solution, then output the word “NULL” (without quotes) on a line of its own. If Omar can visit all the cities with G liters of Gasoline, output “POSSIBLE” (without quotes). Otherwise, If he cannot, output “IMPOSSIBLE” (without quotes).

Sample Input:

4 4 20

0 1 1

1 2 2

1 3 3

2 3 0

2 1 90

0 1 100

3 0

-1 -1 -1

Sample Output:

POSSIBLE

IMPOSSIBLE

NULL

## Clarifications during the contest:

1/ You should connect all the nodes with the minimum cost.

2/ You do not need to repeat the calculation of an edge if you already traversed it.

## Idea:

The idea of the problem is to calculate the minimum spanning tree and compare its value with the initial amount of gasoline. So, if mst <= g, print “POSSIBLE”. If mst > g, print “IMPOSSIBLE”. If the mst = 0 because the driver cannot go anywhere or the graph is not connected output “NULL”.

## Time Complexity:

In my implementation, I used Kruskal’s algorithm to find the minimum spanning tree, so the time complexity is O(E log V)

## Leave a Reply