South African Computer Olympiad 2008 Day 1 Problem 3 - Visiting Grandma

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

Bruce plans to visit his beloved grandmother whom he has not seen in ages. The petrol price is high and the roads are dangerous, so he wants to travel the shortest possible distance. He also wants to know how much choice he has for the route, as he wants to visit his grandmother more often and being Bruce, he loves change.

Bruce wants to surprise his grandmother with a box of cookies every time he visits. Bruce does not know how to make real cookies (digital ones are easy, however!), so he will have to go past a cookie store along the way, possibly increasing the length of the shortest distance.


Bruce will start off in his home town, numbered 1, and his grandmother lives in town N. Given the distance between each pair of towns and the location of the cookie stores, your task is to determine the length of the shortest route and the number of routes having that length. All routes must visit a town with a cookie store. Bruce is only interested in the last six digits of the number of routes, i.e. the remainder after division by 1\,000\,000.

Input Specification

The first line contains a single integer N, representing the number of towns (numbered 1 to N). The next N lines each contain N space-separated integers. The j^{th} integer on the i^{th} line, d_{ij}, is the distance between town i and town j. Following this is a line containing a single integer M, the number of cookie stores. The last line contains M space-separated integers, each representing a town t_j that has a cookie store.

Output Specification

Output two space-separated integers, the length of the shortest route, followed by the remainder when the number of routes having this length is divided by 1\,000\,000.


  • 2 \le N \le 700
  • For 30\% of tests, 2 \le N \le 10.
  • 1 \le t_j, M \le N-1
  • 1 \le d_{ij} \le 1 000 for all i \ne j
  • d_{ii} = 0 (i.e. distance from a town to itself is zero)
  • d_{ij} = d_{ji} (i.e. distance from town i to town j is the same as the distance from town j to town i)

Sample Input

0 2 2 1 1
2 0 1 2 1
2 1 0 2 1
1 2 2 0 2
1 1 1 2 0
2 4

Sample Output

3 4


In the sample input there are 5 towns, with Towns 2 and 4 containing cookie stores. Bruce, who lives in Town 1, wants to visit his grandmother in Town 5. There are four routes having a distance of 3:

  1. Bruce goes from Town 1 \to 2 \to 5 (purchasing cookies at 2)
  2. Bruce goes from Town 1 \to 4 \to 1 \to 5 (purchasing cookies at 4)
  3. Bruce goes from Town 1 \to 4 \to 5 (purchasing cookies at 4)
  4. Bruce goes from Town 1 \to 5 \to 2 \to 5 (purchasing cookies at 2)

Notice that travelling from Town 1 \to 5 directly has a distance of only 1. However, Bruce would then arrive at his grandmother's without any cookies!


  • 3
    Kirito  commented on April 4, 2020, 8:22 p.m.

    What do we output if it is impossible to satisfy the given conditions?

    • 3
      4fecta  commented on April 4, 2020, 8:27 p.m.

      The input format implies that the graph is complete (therefore connected). Also, the lower bound on M is 1, so there is always at least 1 cookie shop Bruce can visit. Thus, there will always be at least one path from town 1 to town N that visits a cookie shop.

      • 0
        pblpbl  commented on April 4, 2020, 9:12 p.m.

        Wait if N = 1, the upper bound for M is N-1 = 0. This may mean that N can't be 1.

        • 0
          yeerk16  commented on April 19, 2020, 6:28 p.m.

          @pblpbl -- I just changed the minimum number of towns to be 2. Thank you for your comment!

  • -1
    pblpbl  commented on April 4, 2020, 4:17 p.m.

    Can paths visit more than one cookie store?