|
|
Chow Number周星驰（Stephen Chow）似乎已成为了当今校园文化的代名词了。 这不，即使是影视圈的明星们，也开始通过”周数“（Chow Number）来衡量自己的艺术水准和文化品味了。 问题所谓的“周数”是一个（随时间不增）的函数： chow() : {所有人} ├→ {0, 1, 2, ..., ∞} 具体的： 1. chow(周星驰) = 0； 2. chow(x) = 1 + min( {∞} U { chow(a) | x与a一起拍过某部电影 } )，x ≠ 周星驰。 任务不幸的是，大多数急于知道自己的Chow Number的人，确实很难坐下来亲自计算一下（他们太忙，另外...）。 作为一名正在学习数据结构的星星的影迷，你是否觉得有责任来编写一个程序帮助他们？ 你编写的程序需要提供以下功能：
例子% chownumber films.dat stars.dat > stars.chow 实现提示这里已经准备好了一个数据库，里面有“所有”影片的信息。 即使对这样小规模的数据，如果直接搜索，程序的速度也很难令人满意，因此这样的实现将不能得分。 幸运的是，最短路径的数据结构及算法可以帮助你：将所有影星表示为图的顶点，在任何曾经合作过的两位影星之间构造一条弧。 如果弧的权值统一为1，那么一个影星的周数实际就是他/她在图中到周星驰的最短路径长。 任务要求的就是找到这样一条最短路径，并输出沿途各弧（合作影片）的信息。 速度测试你可以将自己程序的速度与这个程序对比一下： % chownumber films.dat allstars.dat > allstars.chow 注意，要通过重定向将输出直接记入某个文件，否则，屏幕输出本身就会占用绝大部分时间。 附加功能如果你关心的不止是周数，是否要为每位明星都写一个程序呢？ 试编写一个通用的程序。比如： % chownumber films.dat allstars.dat 孙海鹰 > sunhaiying.chow 或者 % chownumber films.dat allstars.dat 张国荣 > gege.chow
|
|
Copyleft (c) 2003-3002, Junhui Deng |