USACO Cow Routing / Dijkstra's Algorithm

USACO 2015 January Contest, Silver¶

Problem 2. Cow Routing, solved with Dijkstra's Algorithm¶

http://usaco.org/index.php?page=viewproblem2&cpid=512

In [1]:

MAXV = 1001
BIGCOST = 1e12  

# initialize all vertices as unvisited
visited = [False for i in range(MAXV)]

# initialize shortest distance (cost and hops) from A to UNVISITED to "infinity" for all vertices
cost_a2u = [(BIGCOST,MAXV) for i in range(MAXV)]

# initialize cost and hops between all nodes in cost (adjacency) matrix to "infinity"
cost = [[(BIGCOST,MAXV) for i in range(MAXV)] for j in range(MAXV)]   # Need to make a Deep Copy

# set costs to zero from each node to itself
for i in range(MAXV):
    cost[i][i] = (0,0)

In [2]:

fin = open ('cowroute.in', 'r')
fout = open ('cowroute.out', 'w')
A,B,N = map(int, fin.readline().split())
print("Source, Destination, Routes")
print(A,B,N,"\n")

Source, Destination, Routes
3 4 3 

In [3]:

for i in range(N):  
    # read in Route Cost and Number of Flights in route
    route_cost,route_len = map(int, fin.readline().split())
    # read in list of cities along route 
    route = [int(x) for x in fin.readline().split()]
    print(route_cost, route)
    
    # update cost (adjacency) matrix if new route provides lower costs
    for j in range(route_len):
        for k in range(j):
            cost[route[k]][route[j]] = min(cost[route[k]][route[j]],(route_cost,j-k))

3 [1, 2, 3, 4, 5]
2 [3, 5, 4]
1 [1, 5]

In [4]:

# Dijkstra's Algorithm
# Start with the source node, which can reach itself with zero cost and zero hops
cost_a2u[A] = (0,0)

for i in range(MAXV):
    # Find the closest unvisited vertex 
    u = -1
    for j in range(MAXV):
        if visited[j]:
            continue
        # if you encounter your first unvisited node, 
        # or if this node has the lowest costs seen so far,
        # select that node as the closest unvisited node
        elif (u==-1 or cost_a2u[j] < cost_a2u[u]):
            u = j
            
    # SHORTCUT: if u==B, then we are done.  
    # No need to compute the minimum costs to the remaining unvisited nodes
    if u==B:
        break
            
    # "relax" unvisited vertex u
    # i.e., check if path from A to all nodes can be lowered by passing through node u
    visited[u] = True
    rlx_a2u = cost_a2u[u]  # cost tuple from A to U
    for j in range(MAXV):
        # compute cost tuple from A to J through U
        rlx = ( rlx_a2u[0]+cost[u][j][0], rlx_a2u[1]+cost[u][j][1] )
        # check if this cost is better than the current cost from A to J 
        cost_a2u[j] = min(cost_a2u[j], rlx)

In [5]:

# Output the cheapest cost and length if a route exists
ans = cost_a2u[B]
print("Cost, Hops")
if ans[0] < BIGCOST:
    fout.write(str(ans[0])+str(ans[1])+"\n")
    print(ans)
else:
    fout.write("-1 -1\n")
    print("(-1,-1)")

Cost, Hops
(2, 2)