3470. 【NOIP2013模拟联考8】最短路(path) (Standard IO)

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<d[y] then
 47               begin
 48                 d[y]:=d[x]+w;
 49                 if v[y]=0 then
 50                   begin
 51                     t:=t+1;
 52                     list[t]:=y;
 53                     v[y]:=1;
 54                   end;
 55               end;
 56             j:=next;
 57           end;
 58       end;
 59     v[list[h]]:=0;
 60   until h=t;
 61 end;
 62 
 63 procedure search(x:longint);
 64 var
 65   i:longint;
 66 begin
 67   if x=k+1 then
 68     begin
 69       for i:=1 to k do
 70         if bo[i] then exit;
 71       if ans<min then min:=ans;
 72       exit;
 73     end;
 74   for i:=1 to k+1 do
 75     if (top[x,i]>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 do
101         if i<>j then
102           top[i,j]:=d[b[j]];
103     end;
104   fillchar(bo,sizeof(bo),true);
105   for i:=1 to k do
106     if b[i]=s then bo[i]:=false;
107   search(0);
108 end;
109 
110 begin
111   init;
112   main;
113   if min=maxlongint*23333 then writeln('-1')
114                           else writeln(min);
115 end.