大学校区

题目描述:

现在的大学都非常大。中山大学有四个校区，分别是广州北校区、广州南校区、广州东校区和珠海校区。每个校区里面又包含了很多建筑物。有时，老师和学生经常要从某个校区或校区之间的某个建筑物到另外一个建筑物，他们想让你帮忙，计算出它们之间的最短路。

输入格式:

第一行一个数C，表示输入中包括 C组测试数据。对于每组测试数据，第一行为一个整数N(0<n≤100)，表示路的条数。接下来的N 行，第i 行（1≤i≤N）包括两个字符串 Si，Ti和一个整数Di(0≤Di≤100)。表示 Si到Ti有一条长为 Di的路。

最后一行包含两个字符串S 和T，要我们求S 到T 的最短路径。Si，Ti，S，T 的格式都为：Campus.Place(某个校区的某个建筑物)。Campus 用： “North” ， “South” ， “East” ，“Zhuhai” ，代表四个校区的名称，Place 为小于一百个字符的小写字母串，用a-z中的字母表示。

输出格式:

输出共C 行，每行对应一组测试数据。对于每组数据，如果S 到T 有路，输出最短路，否则输出-1。

样例输入:

1
2
South.xiaolitang South.xiongdelong 2
South.xiongdelong Zhuhai.liyuan 100
South.xiongdelong South.xiaolitang

样例输出:

2

时间限制: 1000ms
空间限制: 256MB

---