Description

Input

第一行包含两个整数N、M。N表示路口的个数，M表示道路条数。接下来M行，每行两个整数，这两个整数都在1到N之间，第i+1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行，每行一个整数，按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数S、P，S表示市中心的编号，也就是出发的路口。P表示酒吧数目。接下来的一行中有P个整数，表示P个有酒吧的路口的编号

Output

输出一个整数，表示Banditji从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。

Sample Input

6 7

1 2

2 3

3 5

2 4

4 1

2 6

6 5

10

12

8

16

1 5

1 4

4

3

5

6

Sample Output

47

HINT

 

50%的输入保证N, M<=3000。所有的输入保证N, M<=500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。

 

Source

1A大法爽，由于没有时间的限制，但又因为抢过的ATM没钱了，所以可以tarjan求还然后缩点，再SPFA加了点读入优化，发现慢的1B，WHY？，好像这道T可以DP啊。。。太弱了我。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #define N 500500 8 #define M 500500 9 using namespace std; 10 struct data{ int next,p;}e1[M],e2[M]; 11 int head1[N],head2[N],belong[N],low[N],dfn[N],mon[N],vscc[N],dis[N],inq[N],vis[N]; 12 int q1[N],q[N]; 13 int n,m,S,p,cnt,ans,qt,scc; 14 inline int max(int x,int y){ return x>y?x:y;} 15 inline int min(int x,int y){ return x
            
             ans) ans=dis[belong[x]];109 }110 printf("%d\n",ans);111 return 0;112 }