Rating: 5.0
# \[Misc\] - Cheapest Cookies 2
#### Points = 263
## Prompt
Now that Andrew knows which Costco has the cheapest cookies, he has to get there - as quickly as possible! He has given you 40 roads with the two endpoint locations and the distance of the road, and he starts at location 0 and the Costco is at location 20. All roads are 2-way roads, meaning you can go from x to y and from y to x. Please output the minimum distance needed to reach the Costco, and if there is no possible path, print -1. You will need to pass fifty tests to get the flag. And don't forget to be fast!
Sample Input:
```
0 20 18
4 8 2
0 4 8
4 20 6
```
Sample Output:
```
14
```
`nc tjc.tf 31111`
by andy
#### Hints
\[None\]
## Provided Files
\[None\]
## Write Up
- We are given a set of edges and are asked to find the shortest path between nodes #0 and #20, if it exists.
- This is a single source, shortest-path problem with positive, undirected edges.
- perfect case for Dijkstra's algorithm.
- I have implemented this before in Java and C++ but I'll do it again in python just for the excercise.
- I'll be using `pwntools` because it provides an easy way to make connections
- the code is commented for clarity
```
from pwn import *
# dijkstra
def calculate_path(edges):
# each node has [distance, prev_node, visited]
# for node 0
distance = [[0, 0, True]]
# initialize 20 other nodes
for i in range(20):
distance.append([1000, -1, False])
# source node
src = 0
# priority queue for the closest node
closest = []
while len(edges) != 0:
# loop through all edges for each node
i = 0
while i != len(edges):
# parse the edge data
edge = edges[i].split(' ')
first = int(edge[0])
second = int(edge[1])
weight = int(edge[2])
other = -1
# if the current edge has an end touching the src node
if first == src:
other = second
elif second == src:
other = first
else:
# nothing to be done - move to next edge
i += 1
continue
# process the edge
# remove from the list to avoid reading it twice
edges.pop(i)
# skip the node if visited - shortest path already found
if distance[other][2] == True:
continue
# update the shortest path
if distance[other][0] > (distance[src][0] + weight):
distance[other][0] = distance[src][0] + weight
distance[other][1] = src
# add to the queue
if not closest:
closest.append([distance[other][0], other])
else:
j = 0
while j != len(closest):
if distance[other][0] < closest[j][0]:
break
else:
j += 1
closest.insert(j, [distance[other][0], other])
# no more reachable nodes
if not closest:
break
# pop the closest node to node #0
next_src = closest.pop(0)
src = next_src[1]
# shortest path to 20 is found - no need to keep going
if src == 20:
return distance[20][0]
break
# mark node as visited
distance[src][2] = True
if distance[20][0] == 1000:
# node 20 is unreachable
return -1
else:
return distance[20][0]
# make connection
tgt = remote('tjc.tf', 31111)
# initial prompt is different from subsequent prompts
recieved = tgt.recvuntil(b'answer: ')
recieved = recieved.decode('ascii').split('\n')
# solve case
lines = recieved[10:-2]
ret = str(calculate_path(lines))
tgt.sendline(bytes(ret, 'ascii'))
# print result
recieved = tgt.recvline(b': ')
recieved = recieved.decode('ascii')
print(recieved)
# handle all cases
while True:
# recieve prompt
recieved = tgt.recvuntil(b': ')
recieved = recieved.decode('ascii').split('\n')
# caclulate and send answer
lines = recieved[1:-2]
ret = str(calculate_path(lines))
tgt.sendline(bytes(ret, 'ascii'))
# recieve and print result
recieved = tgt.recvline().decode('ascii')
print(recieved)
if recieved == 'Test 50 passed!\n':
# recv until the end of the flag
lines = tgt.recvuntil(b'}')
lines = lines.decode('ascii').split('\n')
for line in lines:
print(line)
break
```
## Flag
tjctf{w00_w3_have_th3_c00k1es_n0w}
