提示: 欢迎访问OurACM平台。
Problem 1709 公交换乘问题

Accept: 55    Submit: 305
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

乘坐公交是城市中最主要的出行方式之一,选择最优出行线路将为我们节省大量宝贵的时间。
已知城市中的公交线路,以及某次出行的起始车站和目的车站,编程求出最优的出行线路,使得此次出行尽可能少地进行公交换乘。已知通过两个相邻车站间的路程需要1分钟时间,而换乘公交不需要等待时间。请在换乘次数最少的情况下,求出最少需要多少时间才能从起始车站到达目的车站。

Input

第一行有一个整数m(1<=m<=100),表示公交线路的条数。接下来两行,分别表示出行的起始车站和目的车站。接下来有m条公交线路,每条线路包含两个部分,第一行一个数字k(2<=k<=20),表示该线路经过的车站的个数,接下来k个公交车站,按公交车朝某个方向单向运行的顺序给出,每条公交线路都可以双向对称运行。
车站名称由仅包含字母、数字和下划线的字符串构成,其长度不为空且不超过30个字符,不区分大小写。

Output

输出一行两个整数,分别表示出行需要的最少换乘次数和在换乘次数最少的情况下预计需要的最少出行时间。如果无法从起始车站到达目的车站,请输出 “No Solution!”。

Sample Input

3 HongShan_Bridge Railway_Station 4 Hongshan_BRIDGE XiHe Provincial_Hospital DongJieKou 2 Provincial_Hospital Railway_Station 10 HongShan_Bridge JinNiuShan_Park XiHe Fuzhou_Univ_North_Gate Yangnan_Intersetion Realty_Market DongJieKou WuSi_Intersection Provincial_Hospital Railway_Station

Sample Output

1 9

Source

福州大学第六届程序设计竞赛

Submit  Back  Status  Discuss