洛谷P3393逃离僵尸岛 最短路

貌似一直不写题解不太好QAQ 但是找不到题啊...

随便写点水题来补博客吧

题目不pa了，点链接吧...

点我看题

很明显这是道sb题...

思路：  对于每一个僵尸城市预处理其 s 距离内的城市，然后用个cost数组记录点权，然后直接跑spfa就好了。

            看下数据，可以发现如果k值较大有可能会TLE（没测不知道QAQ）。所以加个简单的优化就可以吧（可能吧QAQ）。

            简单的优化就是在预处理的时候如果某一个僵尸城市 s 距离内的城市有另外的僵尸城市，辣么这个僵尸城市可以不入队，这样可以少掉一点重复的无效搜索。

            依旧看一下数据 发现答案会爆 int 所以就记得开 int64(long long)。

所以看数据是可以看出坑点的... (完美避开=v=

然后直接代码吧。

type
  node=record
     y:longint;
     next:longint;
  end;
var  n,m,k,s:longint;
     tot:longint;
     cost1,cost2:longint;
     x,y:longint;
     i:longint;
     cost,first,a:array[0..100050]of longint;
     q:array[0..1000000]of longint;
     e:array[0..400200]of node;
     dist:array[0..100050]of int64;
     v:array[0..100050]of boolean;
procedure adde(x,y:longint);
begin
  e[tot].next:=first[x];
  e[tot].y:=y;
  first[x]:=tot;
  inc(tot);
end;
procedure bfs(x:longint);
var head,tail:longint;
    now,y,i:longint;
begin
  head:=1;
  tail:=1;
  for i:=1 to n do
  dist[i]:=-1;
  dist[x]:=0;
  q[1]:=x;
  while head<=tail do
  begin
    now:=q[head];
    i:=first[now];
    while i<>-1 do
    begin
      y:=e[i].y;
      if (dist[y]<0)and(cost[y]>=0) then
      begin
        dist[y]:=dist[now]+1;
        cost[y]:=cost2;
        if dist[y]<s then
        begin
          inc(tail);
          q[tail]:=y;
        end;
      end;
      i:=e[i].next;
    end;
    inc(head);
  end;
end;
procedure spfa(s:longint);
var
   head,tail:longint;
   now,y,i:longint;
begin
  head:=1;
  tail:=1;
  for i:=1 to n do
  begin
    dist[i]:=1 << 35;
    v[i]:=false;
  end;
  dist[s]:=0;
  q[1]:=s;
  v[s]:=true;
  while head<=tail do
  begin
    now:=q[head];
    i:=first[now];
    while i<>-1 do
    begin
      y:=e[i].y;
      if (dist[y]>dist[now]+cost[y])and(cost[y]>=0) then
      begin
        dist[y]:=dist[now]+cost[y];
        if not v[y] then
        begin
          inc(tail);
          q[tail]:=y;
          v[y]:=true;
        end;
      end;
      i:=e[i].next;
    end;
    inc(head);
    v[now]:=false;
  end;
end;

begin
  read(n,m,k,s);
  read(cost1,cost2);
  for i:=1 to k do
  begin
    read(a[i]);
    cost[a[i]]:=-1;
  end;
  for i:=1 to n do
  first[i]:=-1;
  for i:=1 to m do
  begin
    read(x,y);
    adde(x,y);
    adde(y,x);
  end;
  for i:=1 to k do
  bfs(a[i]);
  for i:=1 to n do
  if cost[i]=0 then cost[i]:=cost1;
  spfa(1);
  writeln(dist[n]-cost[n]);
end.