shunfurh 于 2017.08.31 15:29 提问

Kevin Bacon

Kevin Norwood Bacon (born July 8, 1958) is an American film and theater actor whose notable roles include Animal House, Diner, Footloose, Flatliners, Wild Things, A Few Good Men, Apollo 13, Mystic River, The Woodsman, Trapped, Friday the 13th, Hollow Man, Tremors, Death Sentence, Frost/Nixon, Crazy, Stupid, Love and X-Men: First Class.

Bacon has won Golden Globe and Screen Actors Guild Awards, was nominated for an Emmy Award, and was named by The Guardian as one of the best actors never to have received an Academy Award nomination.

In 2003, Bacon received a star on the Hollywood Walk of Fame.

He was good at playing various roles, and every actor or actress having the honor of being a partner to Bacon is well respected.

Not everybody got a chance to be a partner with Bacon, so many people were content if they managed to play a movie with somebody who had played a movie with Bacon. This gave rise to the so-called Bacon numbers. Nowadays, an advanced Bacon numbers have been invented, it also refer to the box office, when box office is larger, the number k is smaller. For example, An actor who has play in a movie with Bacon, with the number about this movie is k, had advanced Bacon number k. An actor who had not played with Bacon but with somebody(the movie they played together has a number k2) with Bacon number k1 obtained Bacon number k1+k2, and so on. Today, nearly every actor wants to know what the smallest advanced Bacon number he or she has. Your task is to write a program that computes advanced Bacon numbers for a given set of actor.

Input

The input file contains a sequence of actors, each scenario consisting of a movie database and a list of names. A scenario begins with the line "p n", where p and n are natural numbers with 1 <= p <= 32000;1 <= n <= 3000.1 <= k <= 100 000. Following this line are p lines containing descriptions of movies (this is the movie database). A movie is played by a line of the following form:

k LastName1, FirstName1, LastName2, Firstname2, . . . : TitleOfTheMovie

The names and the title may contain any ASCII characters between 32 and 126 except commas and colons. There will always be exactly one space character following each comma. The first name may be abbreviated, but the same name will always be written in the same way.

Example:

John, Belushi, Karen, Allen, Kevin, Bacon: Animal House

After the p movies follow n lines each containing exactly one name in the same format as in the movie database.

The line "0 0" terminates the input.

No name will consist of more than 40 characters. No line in the input file contains more than 250 characters. In each scenario there will be at most 1100 different actors.

Output

For every scenario first print the number of the scenario in the format shown in the sample output. Then print for every actor name in the list of names their advanced Bacon number based on the movies in the movie database of the scenario. The actors should be output in the order given in the input file. Actors that do not have any relation to Bacon via the movies have advanced Bacon number infinity. Adhere to the format shown in the sample output.
Print a blank line after each case.

Sample Input

3 3
3 John, Belushi, Karen, Allen, Kevin, Bacon: Animal House
2 Tom, Hulce, Karen, Allen: Starting Over
1 Hill, Ken, Bob, Stock: kick the ball
John, Belushi
Tom, Hulce
Bob, Stock
0 0
Sample Output

Database 1
John, Belushi: 3
Tom, Hulce: 5
Bob, Stock: infinity

1个回答

caozhy      2017.09.15 23:45

POJ 2139 Six Degrees of Cowvin Bacon
Six Degrees of Cowvin Bacon Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 2986   Accepted: 1390 Description The cows have been making movies lately, so they
Six Degrees of Cowvin Bacon （最短路）
The cows have been making movies lately, so they are ready to play a variant of the famous game "Six Degrees of Kevin Bacon".  The game works like this: each cow is considered to be zero degrees of s
C/B - Six Degrees of Cowvin Bacon(最短路径算法）
The cows have been making movies lately, so they are ready to play a variant of the famous game "Six Degrees of Kevin Bacon". The game works like this: each cow is considered to be zero degrees o
ZOJ 3532 Kevin Bacon 最短路
Kevin Bacon Time Limit: 1 Second      Memory Limit: 65536 KB Kevin Norwood Bacon (born July 8, 1958) is an American film and theater actor whose notable roles include Animal House, Diner, Footlo
Of Envy -Francis Bacon
From : http://www.authorama.com/essays-of-francis-bacon-10.htmlFrancis Bacon (1561-1626) Of Envy　THERE be none of the affections, which have been noted to fascinate or bewitch, but love and en
How To Build CyanogenMod Android (oneplus/bacon) On Linux

Six Degrees of Cowvin Bacon (poj 2139 最短路Floyd)

Machine Learning - A Probabilistic Perspective [Kevin P. Murphy]

Kevin Durant成长之路
Kevin Durant成长之路by JOHN HUNT Sunday, May 27, 2007在这个世界上，有些人是天生的运动员。但Kevin Durant不是。身高6尺10寸，体重225磅的前锋；在他令人称奇的娴熟技术背后，是整整十年的艰辛。凭着强烈的敬业精神与忘我投入，Durant的篮球生涯逐渐走向辉煌。而这一切的基础，就是短短的一句话：“懈怠的天才，必将为勤奋者所超越。”Taras Br
【PDF】《Machine learning A Probabilistic Perspective》 MLAPP；by Kevin Murphy