P3393 逃离僵尸岛

    • 752通过
    • 4.3K提交
  • 题目提供者 kkksc03 吉祥物
  • 评测方式 云端评测
  • 标签 最短路
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

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

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

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

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

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

    输入输出格式

    输入格式:

    第一行4个整数(N,M,K,S)

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

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

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

    输出格式:

    一个整数表示最低花费

    输入输出样例

    输入样例#1: 复制
    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
    输出样例#1: 复制
    11000

    说明

    对于20%数据,N<=50

    对于100%数据,2 ≦ N ≦ 100000, 1 ≦ M ≦ 200000, 0 ≦ K ≦ N - 2, 0 ≦ S ≦ 100000

    1 ≦ P < Q ≦ 100000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。