Problem 2058. -- 划水的魅力

2058: 划水的魅力

Time Limit: 1 Sec  Memory Limit: 512 MB   64bit IO Format: %lld
Submitted: 40  Accepted: 6
[Submit][Status][Web Board]

Description

这个世界有n个城市(城市编号从1到n),人们修了m条路来连接各个城市,但这个世界很奇怪,有的路是单向的,有的路是双向的。
lala住在编号为citya的城市,其中有nn个划水城市,lala很想去划水,
但lala不知道去哪个划水城市走的路程才最短,于是他向你求助,相信聪明的你一定能帮lala找到最短路径!

Input

多组测试数据,每组测试数据输入如下:
第1行两个整数:n(1<n<6000),m(0<m<min(n(n-1)/2,10n) )分别表示城市个数和路的条数。
第2-m+1行,每行四个整数:a(0<a<=n),b(0<b<=n),c(0<=c<=2),d(0<d<10000)表示城市a到城市b之间有条长为d的路,(c=0表示路是双向的,c=1表示路是只能从城市a走到城市b,c=2表示只能从城市b走到城市a),
保证与每个城市相连点的个数不超过20(保证不存在重边和自环)。
第m+2行两个整数:citya(0<citya<=n),nn(0<nn<n)分表示lala所在的城市,和lala想去划水的城市个数。
第m+3行nn个整数:city[1]~city[nn]表示lala想去划水的城市。

Output

每组测试数据,输出如下:
如果能走到其中一个划水城市,找出距离lala路程最短的划水城市(保证这种情况下只存在一个合法解),并输出两部分,第一部分输出路径(10城市个输出一行,"->"不放在行尾),第二部分输出一行路程。
如果都不能走到,输出一行"Let me think again"(输出不含引号)。

Sample Input

4 5
1 3 0 11
1 2 2 5
2 3 2 10
3 4 1 2
2 4 0 3
1 1
2
5 6
1 3 0 11
1 2 2 5
2 3 2 10
3 4 1 2
2 4 0 3
3 5 2 6
2 1
5

Sample Output

1->3->4->2
16
Let me think again

Author

Hu

[Submit][Status][Web Board]