Description

给定一个n个点m条边的有向图，有k个标记点，要求从规定的起点按任意顺序经过所有标记点到达规定的终点，问最短的距离是多少。

 

Input

第一行5个整数n、m、k、s、t，表示点个数、边条数、标记点个数、起点编号、终点编号。

接下来m行每行3个整数x、y、z，表示有一条从x到y的长为z的有向边。

接下来k行每行一个整数表示标记点编号。

 

Output

输出一个整数，表示最短距离，若没有方案可行输出-1。

 

Solutions

起点和每个标记点各跑一次SPFA，建立一个(k+1)*(k+1)的图，爆搜即可。

 

代码

 

1 type  2   arr=record  3     x,y,w,next:longint;  4   end;  5 var  6   nm,n,m,k,s,t:longint;  7   min,ans:int64;  8   d:array [0..100001] of int64;  9   ls,v,list:array [0..100001] of longint; 10   a:array [0..100001] of arr; 11   b:array [0..11] of longint; 12   bo:array [0..11] of boolean; 13   top:array [0..11,0..11] of int64; 14 procedure init; 15 var 16   i,x:longint; 17 begin 18   readln(n,m,k,s,t); 19   for i:=1 to m do 20     begin 21       readln(a[i].x,a[i].y,a[i].w); 22       a[i].next:=ls[a[i].x]; 23       ls[a[i].x]:=i; 24     end; 25   for i:=1 to k do 26     readln(b[i]); 27 end; 28  29 procedure spfa(x:longint); 30 var 31   i,j,k,h,t:longint; 32 begin 33   for i:=0 to 100001 do 34     d[i]:=maxlongint*23333; 35   fillchar(v,sizeof(v),0); 36   fillchar(list,sizeof(list),0); 37   h:=0; t:=1; 38   v[x]:=1; list[1]:=x; d[x]:=0; 39   repeat 40     h:=h+1; 41     j:=ls[list[h]]; 42     while j<>0 do 43       begin 44         with a[j] do 45           begin 46             if d[x]+w
     
      0) and bo[i] then 76       begin 77         bo[i]:=false; 78         ans:=ans+top[x,i]; 79         search(i); 80         bo[i]:=true; 81         ans:=ans-top[x,i]; 82       end; 83 end; 84  85 procedure main; 86 var 87   i,j:longint; 88 begin 89   min:=maxlongint*23333; ans:=0; 90   fillchar(top,sizeof(top),0); 91   spfa(s); 92   if k=0 then 93     if d[t]<>0 then min:=d[t]; 94   for i:=1 to k do 95     top[0,i]:=d[b[i]]; 96   for i:=1 to k do 97     begin 98       spfa(b[i]); 99       top[i,k+1]:=d[t];100       for j:=1 to k do101         if i<>j then102           top[i,j]:=d[b[j]];103     end;104   fillchar(bo,sizeof(bo),true);105   for i:=1 to k do106     if b[i]=s then bo[i]:=false;107   search(0);108 end;109 110 begin111   init;112   main;113   if min=maxlongint*23333 then writeln('-1')114                           else writeln(min);115 end.