We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Floyd : City of Blinding Lights
  5. Discussions

Floyd : City of Blinding Lights

  • zliu046
     + 0 comments

    Pypy will reduce the running time

    follwing will not pass on python3 due to the time call and draw back in loops, but pypy will fine.

    also, min is time consuming (on calling part) compare to > or < as to my test.

    import itertools as ittls


if __name__ == '__main__':
    road_nodes, road_edges = map(int, input().rstrip().split())

    # road_from = [0] * road_edges
    # road_to = [0] * road_edges
    # road_weight = [0] * road_edges

    adjM=[[math.inf]* road_nodes for _ in range(road_nodes)]
    
    for i in range(road_nodes):
        adjM[i][i]=0
    
    for i in range(road_edges):
        road_from, road_to, road_weight= map(int, input().rstrip().split())
        adjM[road_from-1][road_to-1]=road_weight
        
    for k, j, i in ittls.permutations(range(road_nodes),3):
        if adjM[i][j]>adjM[i][k]+adjM[k][j]:
            adjM[i][j]=adjM[i][k]+adjM[k][j]

        
    

    q = int(input().strip())
    
    for q_itr in range(q):
        first_multiple_input = input().rstrip().split()

        x = int(first_multiple_input[0])-1

        y = int(first_multiple_input[1])-1
        a=adjM[x][y]
        
        if a == math.inf:
            print(-1)
        else:
            print(a)