CareerCup

I think some part of the info is missing. :\ When are the holidays? Any sample case?

Obviously you could try all the possible itineraries imaginable with a simple recursive algorithm. As you have to decide not only which roads to go down but when in the week to start a particular trip this becomes rather time consuming for all but the smallest number of cities. It does not say you are forbidden to re-enter a city so this both makes the brute force solution harder it might also suggest you can employ dynamic programming. There are many ways to end up in a city in a given week so we can use dynamic programming. This should get you down to O(cities^2 * weeks)
In any week you will be in a particular city. If you accumulated a lot of gifts getting there that is good. If you walked / drove / rode fewer hours over the weeks to get there even better. There may be many ways to get to a particular city in a particular week. So we can make a matrix of cities and weeks keeping the best course and gift count for each. Actually you can keep just the source city in each cell along with the score. The score would consist of the gift count and the miles. you could combine these into a single number like this:
Gifts + C1*(C2-hours of travel)
Where C1 * C2 < 1 and C2 is larger than all the hours you could travel in a year
This will insure that the number of hours only comes into play if the number of gifts are equal when doing a comparison. Perhaps they do not care about the hours.
Call the matrix m[week][city]
The new score for m[week][city] = the best score of all cities for week-1 such that you can get from the other city to the current one.
Init array M[][] = infinite negative score
Distance between to cities x and y is given by the matrix distance[x][y] if you cannot travel from x to y the value is - infinity.
M[0][start city] = 0
So now just to compute the best score for a simplified version of the problem
For week = 1 to 56
For all cities x
For all cities y
M[week][x] = MAX(M[week-1][ y] + distance[y][x], M[week][x])
Return MAX(M[56][…])
If it takes more than one week to get between two cities then things are more complex.
Also I am assuming by travel once a week it is meant you can only travel between 2 cities and then you must wait till Sunday before you can think about traveling again. The once a week restriction along with the arrive on a particular day restriction may also complicate things as will the need to extract the itinerary.