XZC的毕业旅行计划 Apare_xzc
XZC的毕业旅行计划
时间限制：1000ms
内存限制：256M
题面：
XZC打算毕业旅行，要从出发地出发到达目的地。地图有n个城市，m条双向高铁线路。你能帮他找到一条最省钱，而且中转最少的路线吗？他还是一个学生党，所以首先要保证从出发地到目的地的高铁票费用(因为普快是在是太慢了，他回家要坐20个小时，他受够了这种感觉)和食宿费等最少。在最省钱的基础上，他希望中转的次数最少，毕竟中转是一件很麻烦的事情，人生地不熟的…聪明的你能帮帮他吗?
他有k个询问，每个询问可能有不同的出发和目的地。目的地是要旅行的城市。那么为什么出发地也不同呢？这还不简单？因为他可能在学校，和室友们吃完大餐以后出发，也可能在别的城市，实习完再出发，也可能先回家一趟，收拾好东西从家出发，还可能先去npy家玩一下再一起去旅行23333。对于每个询问，他希望你详细地为他推荐一条价格最便宜，中转还最少的路线。你有一个地图，上面显示了最新的高铁线路和票价。你来帮帮他叭~
输入格式：
- 多组输入（因为高铁票价和线路是动态改变的，所以在输入文件中我们有多组输入）
- 每个测试文件，第一行是一个正整数T(T<=5) 代表数据的组数，接下来是T组数据
- 每组数据的第一行是两个正整数n,m，表示城市的数量和城市间现有的高铁线路个数。其中n<=10,000, m<=100,000。接下来有m行，每行有空格隔开的两个不同的字符串u,v，以及正整数C(C<=100,000)，u,v的长度均小于20。表示u,v这两座城市之间有高铁线路，票价为C。
- 接下来有n行，每行有一个字符串city和一个非负整数x，代表在city这个城市中转的最少花费为x(元)，包括打车费，住宿费(如果需要的话)等等
- 接下来一行有一个正整数k表示询问的个数，k<=2000
- 接下来有k行，每行两个字符串u,v代表出发地为u，目的地为v
输出格式：
- 第k组输入，先输出一行“Case #k:” (不输出引号)
- 每两组输入之间输出两行空行，增强可读性，最后一组输入的最后一个询问后面不输出空行！
- 对于同一组输入中的第i个询问，先输出一行" query (i):"（不输出引号，行首有2个空格），同时两个询问之间输出一个空行，最后一个询问后面不输出空行！
- 对于每个询问的每一行输出，都要有4个空格的缩进。如果出发地或目的地在n个城市中没有，输出相关的提示，见样例； 如果出发地和目的地在地图上n个城市中都有，但是没有高铁线连通，也输出相关提示，见样例。如果有答案，输出最少需要花费的数目，满足最小花费的路线数量，以及给出一条具体的，中转最少的路线。具体格式见样例。
样例输入
4
5 4
A B 1000
B C 2000
A C 355000
E D 4164
A 12
B 21
C 12
D 4
E 9
5
A C
A D
E A
A F
X Y
6 8
Beijing Shanghai 980
Beijing handan 400
Beijing Chongqing 442
Beijing Taiyuan 200
Taiyuan Chongqing 193
Taiyuan handan 150
handan Shanghai 499
Chongqing Shanghai 448
Beijing 113
Shanghai 120
Chongqing 89
Taiyuan 50
handan 80
Yangqu 45
5
Beijing Shanghai
Chongqing Yangqu
Taiyuan London
Tokyo Yangqu
Shanghai Beijing
3 1
London NewYork 803
London 549587
NewYork 779876
Paris 448676
4
NewYork London
London Paris
MianYang Taigu
London NewYork
5 4
A B 1000
B C 2000
A C 355000
E D 4164
A 12
B 21
C 12
D 4
E 9
5
A C
A D
E A
A F
X Y
样例输出：
Case #1:
query (1): from A to C:
The lest cost from A to C is: 3021.
There is only one route which can satisfy the lest cost.
The fewest number of transfer stations can be: 3.
A->B->C.
query (2): from A to D:
Sorry,there are no way from A to D.
query (3): from E to A:
Sorry,there are no way from E to A.
query (4): from A to F:
F is not on this map.
query (5): from X to Y:
X and Y are not on this map.
Case #2:
query (1): from Beijing to Shanghai:
The lest cost from Beijing to Shanghai is: 979.
There are 3 routes which can satisfy the lest cost.
The fewest number of transfer stations can be: 3.
Beijing->Chongqing->Shanghai.
query (2): from Chongqing to Yangqu:
Sorry,there are no way from Chongqing to Yangqu.
query (3): from Taiyuan to London:
London is not on this map.
query (4): from Tokyo to Yangqu:
Tokyo is not on this map.
query (5): from Shanghai to Beijing:
The lest cost from Shanghai to Beijing is: 979.
There are 3 routes which can satisfy the lest cost.
The fewest number of transfer stations can be: 3.
Shanghai->handan->Beijing.
Case #3:
query (1): from NewYork to London:
The lest cost from NewYork to London is: 803.
There is only one route which can satisfy the lest cost.
The fewest number of transfer stations can be: 2.
NewYork->London.
query (2): from London to Paris:
Sorry,there are no way from London to Paris.
query (3): from MianYang to Taigu:
MianYang and Taigu are not on this map.
query (4): from London to NewYork:
The lest cost from London to NewYork is: 803.
There is only one route which can satisfy the lest cost.
The fewest number of transfer stations can be: 2.
London->NewYork.
Case #4:
query (1): from A to C:
The lest cost from A to C is: 3021.
There is only one route which can satisfy the lest cost.
The fewest number of transfer stations can be: 3.
A->B->C.
query (2): from A to D:
Sorry,there are no way from A to D.
query (3): from E to A:
Sorry,there are no way from E to A.
query (4): from A to F:
F is not on this map.
query (5): from X to Y:
X and Y are not on this map.
AC愉快~
xzc
2020/2/11 9:52
投递科大讯飞等公司10个岗位 >
