In the current article I will try to solve a problem for calculation of average distance with Dijkstra, given in codeforces.com contest here in pdf.
What is the problem like?
We have n weighted graphs like this:
For each given graph, we should print the average of all paths in the graph. It is not that trivial, because for the given graph the result looks like this:
(6+3+7+9+9+13+15+10+12+2)/10 = 8.6
E.g. man should consider not only the direct paths, but also the not direct ones and possibly the shortest one if applicable. Thus, having the words “shortest” and “graph” in a task, we go to Dijkstra! 🙂 My solution is not optimal, because I am not using built up classes as stack in order to make it, but it works 🙂
It looks like this:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#Possible input: #1 #5 #0 1 6 #0 2 3 #0 3 7 #3 4 2 #Output: #8.6 def visit_position(list_results,list_visited): #returns the position in list_results of the smallest value, which is not visited list_smallest = [] smallest_value = float('inf') for i in range(0,len(list_visited)): if list_results[i] != float('inf') and list_visited[i] == 0: list_smallest.append(i) for i in range(0, len(list_smallest)): if list_results[list_smallest[i]] |
That is all folks!
Enjoy it in GitHub as well!