The question is:
A given graph is given with only weights 1 or 2 on its arcs. (I.e. each arc has a weight of 1 or a weight of 2)
And a origin vertex s.
Write an efficient algorithm that finds the shortest paths (most easy in weight that is) from s to the rest of the vertices.
I really don't have a better idea than perform the Dijkstra algorithm, but I know it is not the right answer. Help anyone?