UOJ Logo FLYIOI UOJ

FLYIOI

#35. 逃离现场(escape)

故事背景

通过严格的选拔后,Yuyan在全国100万位选手中脱颖而出,终于来到“谁是百万富翁”的录制现场。可就在这时,场馆被恐怖分子袭击了。

题目描述

因为门卫的失误,疏忽将恐怖分子放入了大厦。入侵者袭击了yuyan,yuyan一怒之下化身为若干只蝙蝠,但yuyan的女朋友Lisa(就是假装成yuyan妹妹的那一位)却不会变成蝙蝠。所以现在的当务之急是找到Lisa并让她和所有蝙蝠集合在一点。你的任务就是帮他们找一条最佳路线。
我们可以用一个无向图来表示录制现场。蝙蝠和Lisa走过任何一条边都要付出一定的代价。因为形态不同,蝙蝠和Lisa走同一条边付出的代价可能不同。但是如果某一只蝙蝠与Lisa碰面,那么Lisa由于蝙蝠的引导,以后的所有路程可以不支付代价(也就是相当于当Lisa和某只蝙蝠都走到某点,之后无视Lisa的存在)现在已知所有蝙蝠,Lisa和目标集合点的位置,请你求出所有蝙蝠和Lisa行走代价的和的最小值。

输入

第一行是5个正整数,n,m,k,S,T,分别代表无向图点数,边数,蝙蝠的数量,Lisa所在起点的编号,集合点的编号。
第二行是k个正整数,分别代表每个蝙蝠所在的起点的编号。
接下来有m行,每行有4个正整数,u,v,q,p,分别是该边的起点、终点,蝙蝠通过该路花费的代价,Lisa通过该路花费的代价。

输出

一行,一个整数,所有人物达到终点所需要的代价的和的最小值。

样例输入

5 5 2 3 4
1 5
1 2 3 5
3 2 3 5
2 4 4 9
3 4 9 6
5 4 1 1 

样例输出

13

数据范围

对于30%的数据 n<=200。
对于20%的数据 k<=5,n<=1000,m<=10000。
对于100%的数据 n<=10000,m<=100000,k<=10000,1<=S、T、u、v<=n,1<=p、q<=1000。不保证蝙蝠起点互不相等,数据中可能有重边和自环,保证所有点均能走到T点(即不存在无解情况)

时间限制

3秒