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

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (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.

Task

Bruce will start off in his home town, numbered $1$ $1$ , and his grandmother lives in town $N$ $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$ $1 000 000$ .

Input Specification

The first line contains a single integer $N$ $N$ , representing the number of towns (numbered $1$ $1$ to $N$ $N$ ). The next $N$ $N$ lines each contain $N$ $N$ space-separated integers. The $j^{th}$ $j^{t h}$ integer on the $i^{th}$ $i^{t h}$ line, $d_{ij}$ $d_{i j}$ , is the distance between town $i$ $i$ and town $j$ $j$ . Following this is a line containing a single integer $M$ $M$ , the number of cookie stores. The last line contains $M$ $M$ space-separated integers, each representing a town $t_j$ $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$ $1 000 000$ .

Constraints

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

Sample Input

Copy

Sample Output

Copy

3 4

Explanation

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

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

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

Comments

0

gipi commented on April 5, 2022, 8:17 a.m.

If a shortest path traverses two city with a store each, this counts as a single route or two? i.e. is it a route identified also by which particular city we use for the store?

2

Kirito commented on April 5, 2020, 12:22 a.m.

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

1

4fecta commented on April 5, 2020, 12:27 a.m.

The input format implies that the graph is complete (therefore connected). Also, the lower bound on $M$ $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$ $N$ that visits a cookie shop.

0

pblpbl commented on April 5, 2020, 1:12 a.m. ← edited →

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

1

yeerk16 commented on April 19, 2020, 10:28 p.m. ← edited →

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

0

pblpbl commented on April 4, 2020, 8:17 p.m.

Can paths visit more than one cookie store?

5

richardzhang commented on April 4, 2020, 10:15 p.m. ← edited →

Yes.