提示: 欢迎访问OurACM平台。
Problem 1852 Impossible Mission II

Accept: 82    Submit: 319
Time Limit: 2000 mSec    Memory Limit : 32768 KB

Problem Description

“活着,一定是没有意义的。但是活下去的话,说不定却能遇见有趣的东西。如你遇见这花,如我遇见你。” — 岸本齐史

ccQ毕业前找到了一个好工作,正准备和MM一起庆祝去旅游。但是MM还要求在到目的地之前,一定要先去逛一些她向往已久的城市。这时ccQ就烦恼了,不同城市之间火车票价不同,ccQ想知道如何设计安排合理的线路能顺利地到达目的地,并且能使得他们在到达目的地之前至少经过MM想去的所有的那些城市而使得总费用最少?ccQ为了使MM满意,请你帮他解决这个问题。

Input

输入有多组数据
每组数据第一行有4个整数,n,m,s,t(n <= 100,m <= n*(n-1)/2,0 <= s,t < n),分别表示总的城市数,城市间的线路数,ccQ他们出发时所在城市,以及ccQ他们所要到达的目的地城市。
接下来m行,每行有三个整数a,b,c,(0 <= a,b < n, c < 70000 )代表城市a和城市b之间有一条双向的铁路,票价为c。
有一个整数k(0 <= k <= 16),代表MM想去的城市数,
接下来k个数代表MM想去的城市。(这些城市不与起始城市与目的地城市重复)

Output

如果ccQ找不到合理的线路那么输出”ccQ is not a lucky boy!”(不包含引号) 否则输出能满足MM要求的线路的最小费用。

Sample Input

4 4 0 3 0 1 2 1 2 5 0 2 10 0 3 2 2 1 2 4 4 0 3 0 1 2 1 2 5 0 2 10 0 3 2 0 4 3 0 3 0 1 2 1 2 5 0 2 10 2 1 2

Sample Output

16 2 ccQ is not a lucky boy!

Source

FOJ有奖月赛-2009年10月——稚鹰翱翔

Submit  Back  Status  Discuss