最短路径问题
我看到这样一道题目
SHORTEST PATH IMPLEMENTATION
Problem Definition
Six Degrees of Kevin Bacon is a trivia game, which is based on a variation of the concept of the small world phenomenon. It states that any actor can be linked to Kevin Bacon through their roles. Once an actor is selected, you try to connect him/her to Kevin
Bacon as quickly as possible and in as few links (via the films they 've shared with other actors). The game has further expansions. In one of these expansions, the goal is to link
two different actors with a path that passes through Kevin Bacon.
Specifications
You first read the actor/movie information from the standard input line by line. Each line
should be of the form:
Actor’s Name#Movie Name
There should be a number sign (#) between the name of the actor and the name of the movie.
Once the whole actor/movie information is read, you will construct a graph by using this data.
For example, if you consider the following input:
Kevin Bacon#Apollo 13
Tom Hanks#Apollo 13
Kevin Costner#JFK
Kevin Bacon#JFK
Gary Oldman#JFK
Kevin Bacon#Mystic River
Sean Penn#Mystic River
Tim Robbins#Mystic River
Bruce Willis#The Fifth Element
Gary Oldman#The Fifth Element
Matt Damon#Saving Private Ryan
Tom Hanks#Saving Private Ryan
Vin Diesel#Saving Private Ryan
Vin Diesel#xXx
Samuel L. Jackson#xXx
Bruce Willis#Pulp Fiction
Samuel L. Jackson#Pulp Fiction
John Travolta#Pulp Fiction
Bruce Willis#Armageddon
Ben Affleck#Armageddon
Steve Buscemi#Armageddon
Matt Damon#Good Will Hunting
Ben Affleck#Good Will Hunting
the constructed graph should be as follows:
这里不能贴图， 我解释一下， 比如说对于这三个输入：
Matt Damon#Saving Private Ryan
Tom Hanks#Saving Private Ryan
Vin Diesel#Saving Private Ryan
应该构造三个节点，是人名，每两个节点之间都用一个名为Saving Private Ryan的链接相连。
The last input should be the line containing the names of the actors that will be linked via Kevin Bacon. The format of this line should be as follows:
Actor1&Actor2
There should be an ampersand sign (&) between the actor names.
After reading the actor names, you will compute the shortest path between these actors that pass through Kevin Bacon and then display the result in the following format:
Actor1 was in Movie with ActorA
ActorA was in Movie with ActorB
ActorB was in …
…
ActorI was in Movie with Kevin Bacon
Kevin Bacon was in Movie with ActorJ
ActorJ was in …
… with ActorN
ActorN was in Movie with Actor2
Note that the path should not contain cycles, i.e. an actor can occur only once on the path.
For example, for the given sample input if the actors to be linked are:
Bruce Willis&Matt Damon
the output should be:
Bruce Willis was in The Fifth Element with Gary Oldman
Gary Oldman was in JFK with Kevin Bacon
Kevin Bacon was in Apollo 13 with Tom Hanks
Tom Hanks was in Saving Private Ryan with Matt Damon
我碰到两个问题解决不了，
1. 如何存储这张图
2. 如何搜索最短路径，我的想法是用floyd算法分别求出起点到Kevin的路径和Kevin到终点的路径。
有谁能提供C++代码，不甚感激。
谢谢大家帮助。
[解决办法]
你都这样说了，兄弟就顶你一下吧！
[解决办法]
我也不顾老脸了，顶！！！！！
[解决办法]
来学习了！顶！！！
[解决办法]
TOPCODER 上的
[解决办法]
拣分
ＬＺ 翻译下题目
[解决办法]
学习
[解决办法]
up,看了一下，学习
[解决办法]
水平还未达到...友情顶贴.呵呵
