题目描述：
-
总时间限制:
- 1000ms 内存限制:
- 65535kB
-
描述
-
很久很久之前，森林里住着一群兔子。有一天，兔子们希望去赏樱花，但当他们到了上野公园门口却忘记了带地图。现在兔子们想求助于你来帮他们找到公园里的最短路。
输入
-
输入分为三个部分。
第一个部分有P+1行（P<30），第一行为一个整数P，之后的P行表示上野公园的地点。
第二个部分有Q+1行（Q<50），第一行为一个整数Q，之后的Q行每行分别为两个字符串与一个整数，表示这两点有直线的道路，并显示二者之间的矩离（单位为米）。
第三个部分有R+1行（R<20），第一行为一个整数R，之后的R行每行为两个字符串，表示需要求的路线。 输出
- 输出有R行，分别表示每个路线最短的走法。其中两个点之间，用->(矩离)->相隔。 样例输入
-
6 Ginza Sensouji Shinjukugyoen Uenokouen Yoyogikouen Meijishinguu 6 Ginza Sensouji 80 Shinjukugyoen Sensouji 40 Ginza Uenokouen 35 Uenokouen Shinjukugyoen 85 Sensouji Meijishinguu 60 Meijishinguu Yoyogikouen 35 2 Uenokouen Yoyogikouen Meijishinguu Meijishinguu
样例输出
-
Uenokouen->(35)->Ginza->(80)->Sensouji->(60)->Meijishinguu->(35)->Yoyogikouen Meijishinguu
题目思路：
题目中给定一些公园的地点，然后给出某些地点存在的路径以及路长，要求出任意的某两个地点之间的最短路，按照格式打印路径。因为是求任意两点之间的最短路。并且数据的范围并不是很大，因此采用Floyd算法。该题目的难点在于建图和路径的记录。因为题目中给出的地点是给定的字符串，而不是编号，因此我们需要使用 map来将地点编号，以方便数据的处理。在记录路径的时候，我们在更新最短路径的地方进行松弛操作。用point[i][j]的值来表示从i点出发到j点的最短路中i点的下一个结点。
题目代码：
# include <cstdio>
# include <map>
# include <iostream>
# define INF 1000000
using namespace std;map<string, int>map1;
map<int, string>map2;
int dist[35][35];
int point[35][35];
int p, q, r, d;
string t1, t2;void init()
{ //dist[i][j]表示i到j的最短距离 for(int i = 0; i < 35; i++){for(int j = 0; j < 35; j++){dist[i][j] = INF;}dist[i][i] = 0;}//point[i][j]表示从i到j的最短路线从i出发的下一个结点 for (int i=0; i<35; i++) { for (int j=0; j<35; j++) { point[i][j] = j; } } //将地点编号 scanf("%d",&p);for(int i = 0; i < p; i++ ){cin>>t1;map1[t1] = i;map2[i] = t1;}//初始化距离 scanf("%d",&q);for(int i = 0; i < q; i++ ){cin>>t1>>t2>>d;dist[map1[t1]][map1[t2]] = dist[map1[t2]][map1[t1]] = d;}}
//求出2点间最短距离
void floyd()
{for(int k = 0; k < p; k++){for(int i = 0; i < p; i++){for(int j = 0; j < p; j++){if(dist[i][j] > dist[i][k] + dist[k][j]){dist[i][j] = dist[i][k] + dist[k][j];//维护从i到j的最短距离从i出发的下一个结点 point[i][j] = point[i][k];}}}}
}int main()
{init();floyd();cin>>r;while(r--){cin>>t1>>t2;//从起点出发的下一个结点 int k = point[map1[t1]][map1[t2]];if(t1 != t2){cout<<t1<<"->("<<dist[map1[t1]][k]<<")->";while(k != map1[t2]){cout<<map2[k]<<"->("<<dist[k][point[k][map1[t2]]]<<")->";//更新下一结点 k = point[k][map1[t2]];}}cout<<t2<<endl;}return 0;
}