

import numpy as np




def     a__  (	UpperCAmelCase							:    Optional[int]       ,				UpperCAmelCase							:    Tuple    )						->		Optional[int]:
  UpperCAmelCase :							int								=				np.array(UpperCAmelCase    )
  UpperCAmelCase :							Tuple								=				np.array(UpperCAmelCase    )

  UpperCAmelCase :							Dict								=				abs(predict - actual    )
  UpperCAmelCase :							Optional[int]								=				difference.mean()

  return score




def     a__  (	UpperCAmelCase							:    Optional[Any]       ,				UpperCAmelCase							:    List[str]    )						->		Any:
  UpperCAmelCase :							List[str]								=				np.array(UpperCAmelCase    )
  UpperCAmelCase :							Optional[int]								=				np.array(UpperCAmelCase    )

  UpperCAmelCase :							Optional[int]								=				predict - actual
  UpperCAmelCase :							List[str]								=				np.square(UpperCAmelCase    )

  UpperCAmelCase :							Optional[int]								=				square_diff.mean()
  return score




def     a__  (	UpperCAmelCase							:    Dict       ,				UpperCAmelCase							:    int    )						->		str:
  UpperCAmelCase :							List[str]								=				np.array(UpperCAmelCase    )
  UpperCAmelCase :							Tuple								=				np.array(UpperCAmelCase    )

  UpperCAmelCase :							int								=				predict - actual
  UpperCAmelCase :							Union[str, Any]								=				np.square(UpperCAmelCase    )
  UpperCAmelCase :							List[Any]								=				square_diff.mean()
  UpperCAmelCase :							Tuple								=				np.sqrt(UpperCAmelCase    )
  return score




def     a__  (	UpperCAmelCase							:    Optional[Any]       ,				UpperCAmelCase							:    List[Any]    )						->		Any:
  UpperCAmelCase :							List[Any]								=				np.array(UpperCAmelCase    )
  UpperCAmelCase :							List[str]								=				np.array(UpperCAmelCase    )

  UpperCAmelCase :							Tuple								=				np.log(predict + 1    )
  UpperCAmelCase :							int								=				np.log(actual + 1    )

  UpperCAmelCase :							Union[str, Any]								=				log_predict - log_actual
  UpperCAmelCase :							List[Any]								=				np.square(UpperCAmelCase    )
  UpperCAmelCase :							Tuple								=				square_diff.mean()

  UpperCAmelCase :							int								=				np.sqrt(UpperCAmelCase    )

  return score




def     a__  (	UpperCAmelCase							:    Union[str, Any]       ,				UpperCAmelCase							:    str    )						->		Union[str, Any]:
  UpperCAmelCase :							List[str]								=				np.array(UpperCAmelCase    )
  UpperCAmelCase :							Union[str, Any]								=				np.array(UpperCAmelCase    )

  UpperCAmelCase :							int								=				predict - actual
  UpperCAmelCase :							Tuple								=				np.sum(UpperCAmelCase    ) / len(UpperCAmelCase    )
  UpperCAmelCase :							Optional[Any]								=				np.sum(UpperCAmelCase    ) / len(UpperCAmelCase    )
  # print(numerator, denumerator)
  UpperCAmelCase :							Dict								=				float(UpperCAmelCase    ) / denumerator * 100

  return score






def     a__  (	UpperCAmelCase							:    Dict       ,				UpperCAmelCase							:    Dict    )						->		int:
  return np.mean(np.array(UpperCAmelCase    ) == np.array(UpperCAmelCase    )    )








def     a__  (	UpperCAmelCase							:    List[str]       ,				UpperCAmelCase							:    List[Any]    )						->		Optional[int]:
  print('''\nVertex Distance'''    )
  for i in range(UpperCAmelCase    ):
    if dist[i] != float('''inf'''    ):
      print(UpperCAmelCase       ,				'''\t'''       ,				int(dist[i]    )       ,				end='''\t'''    )
    else:
      print(UpperCAmelCase       ,				'''\t'''       ,				'''INF'''       ,				end='''\t'''    )
    print()

def     a__  (	UpperCAmelCase							:    Tuple       ,				UpperCAmelCase							:    Optional[int]       ,				UpperCAmelCase							:    Optional[int]    )						->		Any:
  UpperCAmelCase :							Union[str, Any]								=				float('''inf'''    )
  UpperCAmelCase :							str								=				-1
  for i in range(UpperCAmelCase    ):
    if (not vset[i]) and mdist[i] < min_val:
      UpperCAmelCase :							int								=				i
      UpperCAmelCase :							Union[str, Any]								=				mdist[i]
  return min_ind

def     a__  (	UpperCAmelCase							:    Union[str, Any]       ,				UpperCAmelCase							:    Optional[Any]       ,				UpperCAmelCase							:    str    )						->		Tuple:
  UpperCAmelCase :							str								=				[float('''inf'''    ) for _ in range(UpperCAmelCase    )]
  UpperCAmelCase :							Optional[int]								=				[False for _ in range(UpperCAmelCase    )]
  UpperCAmelCase :							List[Any]								=				0.0

  for _ in range(v - 1    ):
    UpperCAmelCase :							Any								=				min_dist(UpperCAmelCase       ,				UpperCAmelCase       ,				UpperCAmelCase    )
    UpperCAmelCase :							List[Any]								=				True

    for i in range(UpperCAmelCase    ):
      if (
          (not vset[i])
          and graph[u][i] != float('''inf'''    )
          and mdist[u] + graph[u][i] < mdist[i]
      ):
        UpperCAmelCase :							str								=				mdist[u] + graph[u][i]

  print_dist(UpperCAmelCase       ,				UpperCAmelCase    )


if __name__ == "__main__":
     _lowerCamelCase       :     Tuple           =							int(input("Enter number of vertices: ").strip())
     _lowerCamelCase       :     List[str]           =							int(input("Enter number of edges: ").strip())

     _lowerCamelCase       :     Optional[int]           =							[[float("inf") for i in range(V)] for j in range(V)]

     for i in range(V):
          _lowerCamelCase       :     Union[str, Any]           =							0.0

     for i in range(E):
          print("\nEdge ", i + 1)
          _lowerCamelCase       :     List[str]           =							int(input("Enter source:").strip())
          _lowerCamelCase       :     List[str]           =							int(input("Enter destination:").strip())
          _lowerCamelCase       :     List[Any]           =							float(input("Enter weight:").strip())
          _lowerCamelCase       :     Any           =							weight

     _lowerCamelCase       :     List[str]           =							int(input("\nEnter shortest path source:").strip())
     dijkstra(graph, V, gsrc)





