Want to try solving this problem? You can submit your code online if you log in or register.

**Input File:** `drivein.txt`

**Output File:** `driveout.txt`

**Time Limit:** 1 second

**Memory Limit:** 32 MB

It is a bright Sunday morning, and your favourite thing to do on a Sunday morning is to drive around the town playing loud music with your car windows down. Unfortunately, not everybody in the town shares your taste in music.

The CD in your car contains *S* songs. Each song is of a particular
style of music, such as jazz, pop or classical. Each street in the town
has its own favourite style of music, and if you drive along a street
playing the wrong style of music then the residents will throw eggs at
your car. Clearly you would prefer this not to happen.

The town consists of *N* intersections and *T* streets,
where each street
joins two intersections. Each song on your CD plays for only one
street — when you reach an intersection, the turning movement of the car
makes the CD jump directly to the next song.

You wish to plan your drive so that you have as few eggs thrown at you as
possible. Your drive must begin at your house, which lies at one of the
intersections. Your drive must also end at your house, and it must
pass through precisely *S* streets along the way. Streets may be used more
than once; you may even make a U-turn at an intersection and drive back down
the street along which you came (although you may not make a U-turn in the
middle of a street).

As an example, consider the town illustrated below. There are
*N* = 5
intersections in the town, and *T* = 6 streets joining them.
Your house is at intersection 1.

Suppose your CD contains *S* = 7 songs, which
have the following styles in order from first to last:

Jazz ; Classical ; Classical ; Pop ; Classical ; Pop ; JazzA good drive might be the following:

Song number | Street | CD style | Street style |

1. | 1-2 | Jazz | Jazz |

2. | 2-4 | Classical | Classical |

3. | 4-2 | Classical | Classical |

4. | 2-3 | Pop | Jazz |

5. | 3-5 | Classical | Classical |

6. | 5-4 | Pop | Pop |

7. | 4-1 | Jazz | Pop |

For songs number 1, 2, 3, 5 and 6, your song matches the favourite style of the street and the residents throw you flowers and kisses. For songs number 4 and 7, your song does not match and the residents throw eggs at your car.

Your task is to choose the *S* streets of your drive so that eggs are
thrown at you as few times as possible.

The first line of input will contain the single integer *S*, giving the
number of songs on your CD
(1 <= *S* <= 500).

The second line of input will describe the style of each song on the CD.
For simplicity, each style is described by an integer in the range
1,2,...,20000. The second line of input will therefore consist of
*S*
positive integers separated by spaces, giving the style of each song on the
CD in order from the first song to the last song.

The third line of input will contain the two integers *N* and
*H* separated
by a single space, where *N* is the number of intersections
(1 <= *N* <= 200) and
*H* is the intersection at which you must start and
finish
(1 <= *H* <= *N*).

The fourth line of input will contain the single integer *T*, giving the
number of streets
(0 <= *T* <= 20,000).
Following this will be *T*
additional lines, each describing a single street. Each of these lines will
contain three integers *X Y M* separated by single spaces, where the street
joins intersections *X* and *Y*
(1 <= *X*,*Y* <= *N*),
and where *M* is
the favourite style of music for the street
(1 <= *M* <= 20,000). No
street will join an intersection with itself (that is,
*X* ≠ *Y*), and no
pair of intersections will be joined by more than one street.
All streets are two-way (i.e., you may drive along them in either direction).

It is guaranteed that it is possible to drive from intersection *H* back to
intersection *H* again by following precisely *S* streets.

Output must consist of a single integer, giving the smallest possible number of streets on which the residents throw eggs at you.

The following sample input and output describe the scenario illustrated earlier. Music styles 1, 2 and 3 correspond to jazz, classical and pop respectively.

7 1 2 2 3 2 3 1 5 1 6 1 2 1 1 4 3 2 3 1 2 4 2 3 5 2 4 5 3

2

The score for each input scenario will be 100% if the correct answer is output, or 0% otherwise.

Privacy
statement

© Australian Mathematics Trust 2001-2022

Page generated: 25 September 2022, 2:57am AEST