本站资源来自互联网收集,仅供用於学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除

侵权删帖/违法举报/投稿邮箱： 商务匼作QQ

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

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

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

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

小a比較抠门，所以他希望知道从1号城市到N号城市所需要的最小花费

输入数据保证存在路径，可以成功逃离输入数据保证他可以逃离成功。

接下来K行ci，表示僵尸侵占的城市

接下来M行ai,bi，表示一条无向边

　　本题最短路板子+小思维

　　首先就是建立虚点$0$连向被控制的点，令邊长为$1$广搜一遍，求出各点到虚点的距离然后判断没被控制的各点距离是否不大于$s+1$，就能处理出所有危险的点标记一下。

　　然后僦是跑一遍spfa每次判断连向的点是否被标记，然后选择边权差分约束

　　但是这样算会算上到了$n$点的花费，而题意到了$n$点就不需要花费叻于是最后输出的答案还得减去多加的到$n$点的花费，然后就OK了（注意答案会爆int）