【题解】LuoGu3393：逃离僵尸岛

原题传送门
题目描述

小a住的国家被僵尸侵略了&＃xff01;小a打算逃离到该国唯一的国际空港逃出这个国家。

该国有N个城市&＃xff0c;城市之间有道路相连。一共有M条双向道路。保证没有自环和重边。

K个城市已经被僵尸控制了&＃xff0c;如果贸然闯入就会被感染TAT…所以不能进入。由其中任意城市经过不超过S条道路就可以到达的别的城市&＃xff0c;就是危险城市。换句话说只要某个没有被占城市到某个被占城市不超过s距离&＃xff0c;就是危险。

小a住在1号城市&＃xff0c;国际空港在N号城市&＃xff0c;这两座城市没有被侵略。小a走每一段道路&＃xff08;从一个城市直接到达另外一个城市&＃xff09;得花一整个白天&＃xff0c;所以晚上要住旅店。安全的的城市旅馆比较便宜要P元&＃xff0c;而被危险的城市&＃xff0c;旅馆要进行安保措施&＃xff0c;所以会变贵&＃xff0c;为Q元。所有危险的城市的住宿价格一样&＃xff0c;安全的城市也是。在1号城市和N城市&＃xff0c;不需要住店。

小a比较抠门&＃xff0c;所以他希望知道从1号城市到N号城市所需要的最小花费。

输入数据保证存在路径&＃xff0c;可以成功逃离。输入数据保证他可以逃离成功。

输入输出格式

输入格式&＃xff1a;
第一行4个整数(N,M,K,S)

第二行2个整数(P,Q)

接下来K行&＃xff0c;ci&＃xff0c;表示僵尸侵占的城市

接下来M行&＃xff0c;ai,bi&＃xff0c;表示一条无向边

输出格式&＃xff1a;
一个整数表示最低花费
输入样例
13 21 1 1
1000 6000
7
1 2
3 7
2 4
5 8
8 9
2 5
3 4
4 7
9 10
10 11
5 9
7 12
3 6
4 5
1 3
11 12
6 7
8 11
6 13
7 8
12 13
输出样例
11000
对于100%数据&＃xff0c;2 ≦ N ≦ 100000, 1 ≦ M ≦ 200000, 0 ≦ K ≦ N - 2, 0 ≦ S ≦ 100000

【题解】
读完题目我发现这是一道裸的最短路~~~
只是多了一个判断是否为危险城市的步骤
本题分为以下几个步骤

• 把感染的城市标记&＃xff0c;这些城市是不通的&＃xff0c;并放进一个bfs队列
• 从感染的城市出发进行bfs&＃xff0c;把遍历到的距离<&＃61;s的标记为危险城市&＃xff08;危险城市与感染城市是不同的&＃xff09;
• 以1为起点&＃xff0c;做最短路&＃xff0c;我刚学了dijkstra堆优化&＃xff0c;所以用了这个方法&＃xff0c;本题也可以用SPFA

嗯没错&＃xff0c;这就是一道模板题&＃xff0c;解释一下我的代码的各个变量的用途

• heap 堆&＃xff08;由于我用的是pascal&＃xff0c;所以是手打堆&＃xff09;
• q,d 用于bfs&＃xff0c;q记录点的序号&＃xff0c;d记录该点离最近的感染城市的距离
• edge,head 数组模拟链表存图
• flag 标记感染城市 danger 标记危险城市 vis 用于dijkstra
• dis 表示距离&＃xff0c;用于dijkstra

注意&＃xff1a;开int64(long long)&＃xff0c;并且初始化dis也要弄得很大很大&＃xff0c;比2147483647还要大

Code&＃xff1a;

varheap:array[0..1000000] of recordnum,dis:int64;end;edge:array[0..1000000] of recordt,next:int64;end;head,q,d,dis:array[0..1000000] of int64;vis,danger,flag:array[0..1000000] of boolean;n,m,k,s,p,qq,x,y,z,h,t,num,len,e,w:int64;i:longint;procedure add(x,y:int64);begininc(num);edge[num].t :&＃61; y;edge[num].next :&＃61; head[x];head[x] :&＃61; num;
end;procedure swap(var x,y:int64);
vartmp:int64;begintmp :&＃61; x; x :&＃61; y; y :&＃61; tmp;
end;procedure push(x,y:int64);
vari:longint;begininc(len);heap[len].num :&＃61; x; heap[len].dis :&＃61; y;i :&＃61; len;while i > 1 dobeginif heap[i].dis > 1].dis thenbeginswap(heap[i].num,heap[i >> 1].num);swap(heap[i].dis,heap[i >> 1].dis);i :&＃61; i >> 1;end else break;end;
end;procedure pop;
vari,x:longint;beginheap[1].num :&＃61; heap[len].num; heap[1].dis :&＃61; heap[len].dis;dec(len); i :&＃61; 1;while (i <<1) <&＃61; len dobeginif ((i <<1 or 1) > len) or (heap[i <<1].dis 1 or 1].dis) thenx :&＃61; i <<1 else x :&＃61; i <<1 or 1;if heap[i].dis > heap[x].dis thenbeginswap(heap[i].num,heap[x].num);swap(heap[i].dis,heap[x].dis);i :&＃61; x;end else break;end;
end;beginreadln(n,m,k,s);readln(p,qq);for i :&＃61; 1 to k dobeginreadln(q[i]);flag[q[i]] :&＃61; true;end;for i :&＃61; 1 to m dobeginreadln(x,y);add(x,y); add(y,x);end;t :&＃61; k;while h dobegininc(h);if d[h] &＃61; s then break;i :&＃61; head[q[h]];while i <> 0 dobegine :&＃61; edge[i].t;if not danger[e] thenbegindanger[e] :&＃61; true;inc(t);q[t] :&＃61; e; d[t] :&＃61; d[h] &＃43; 1;end;i :&＃61; edge[i].next;end;end;for i :&＃61; 2 to n do dis[i] :&＃61; maxlongint * maxlongint;heap[1].num :&＃61; 1; heap[1].dis :&＃61; 0; len :&＃61; 1;while len > 0 dobeginx :&＃61; heap[1].num; y :&＃61; heap[1].dis;pop;if vis[x] then continue;vis[x] :&＃61; true;i :&＃61; head[x];while i <> 0 dobegine :&＃61; edge[i].t;if flag[e] thenbegini :&＃61; edge[i].next;continue;end;if danger[e] then w :&＃61; qq else w :&＃61; p;if e &＃61; n then w :&＃61; 0;if dis[e] > y &＃43; w thenbegindis[e] :&＃61; y &＃43; w;push(e,dis[e]);end;i :&＃61; edge[i].next;end;end;writeln(dis[n]);
end.