Lynbrook Computer Science

Welcome to a new semester of school and, of course, of CS Club!

Today we discussed one possible solution to the Problem of the Week (the problem actually lasted an entire month), and presented Dijkstra’s Algorithm.

The new Problem of the Week is as follows:

• Today, Bessie wants to take a trip to a city, but doesn’t know where yet. She has x dollars to spend, and the airline she is using charges $1 per mile. Tell her how many cities she might be able to visit, if she starts at node #1. Please note that all possible flights are one-way only, and after visiting her destination, she must also return. She can also take as many flights as she wants. Please also include node #1 in your count.
• Assume that every city is visitable from every other city given an infinite amount of money.
• Also assume that all plane flight distances are less than 1000.
• Let N=# of cities, and M=# of flights.
• For 25 points, solve for N<100 and M<100
• For 40 points, solve for N<10000 and M<100000

Sample input:
11   (x)
4 6   (# of cities, # of flights)
1 2 1   (flight #1: city #1, city #2, then distance in miles)
2 3 3   (flight #2)
1 3 6   (etc.)
3 1 7
3 4 6
4 1 2
Sample output:
3 (she can visit nodes #1,2, or 3, but not 4)

The problem can also be found, along with some hints, in the meeting slides.

Note that today is the last day to take the January USACO! Because the problems are harder this month, you are given four hours for the contest, rather than three. As usual, participation counts for 5 points towards your PotW score. Happy coding!