题目描述
小 a 住的国家被僵尸侵略了！小 a 打算逃离到该国唯一的国际空港逃出这个国家。
该国有 $N$ 个城市，城市之间有道路相连。一共有 $M$ 条双向道路。保证没有自环和重边。
其中 $K$ 个城市已经被僵尸控制了，如果贸然闯入就会被感染 TAT…所以不能进入。由其中任意城市经过不超过 $S$ 条道路就可以到达的别的城市，就是危险城市。换句话说只要某个城市到任意被僵尸控制的城市距离不超过 $S$，就是危险的。
小 a 住在 $1$ 号城市，国际空港在 $N$ 号城市，这两座城市没有被侵略。小a走每一段道路（从一个城市直接到达另外一个城市）得花一整个白天，所以晚上要住旅店。安全的的城市旅馆比较便宜要 $P$ 元，而被危险的城市，旅馆要进行安保措施，所以会变贵，为 $Q$ 元。所有危险的城市的住宿价格一样，安全的城市也是。在 $1$ 号城市和 $N$ 城市，不需要住店。
小 a 比较抠门，所以他希望知道从 $1$ 号城市到 $N$ 号城市所需要的最小花费。
输入数据保证存在路径，可以成功逃离。输入数据保证他可以逃离成功。
输入格式
第一行 4 个整数 $N,M,K,S$。
第二行两个整数 $P,Q$。
接下来 $K$ 行，每行一个整数 $c_i$，表示僵尸侵占的城市编号。
接下来 $M$ 行，$a_i,b_i$，表示一条无向边。
输出格式
一个整数表示最低花费。
思路：bfs，最短路
使用邻接表建图，此处略。
注意无向图的二倍空间。
僵尸的处理
首先使用 $zombie[i]$ 数组记录第 $i$ 个点是否被僵尸占领。
对于被僵尸占领的点，不能经过它，并且对它 $S$ 格以内的点标记上危险，使用 $exps[x]$ 表示第 $x$ 个点是否危险（价格贵）。
此处使用广度优先，使用深度优先可能会出错或时间复杂度较高。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void mark(int x) {
auto q = queue<pair<int, int>>();
q.push({x, 0});
vis[x] = true;
while(q.size()) {
auto n = q.front();
q.pop();
exps[n.first] = true;
if(n.second < S) {
for(int i = head[n.first]; i; i = edge[i].next) {
int to = edge[i].to;
if(vis[to]) continue;
vis[to] = true;
q.push({to, n.second + 1});
}
}
}
}
|
点权转换
可以考虑，$1$ 号点到 $i$ 号点的消费为“路径长度”。
这样就转化为了最短路问题。
最短路
有僵尸的点跳过。
考虑使用 $money$ 数组（长度为 $2$）记录普通和危险节点的价格。
这样，第 $i$ 个点的价格为：$money[exps[i]]$，从而简化思路。
注意会爆int！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| ll min_cost() {
set(dis, inf);
dis[1] = 0;
priority_queue<node> q;
q.push({1});
while(q.size()) {
int from = q.top().from;
vis[from] = true;
q.pop();
for(int i = head[from]; i; i = edge[i].next) {
int to = edge[i].to;
if(vis[to]) continue;
if(zombie[to]) continue;
if(dis[from] + money[exps[to]] < dis[to]) {
dis[to] = dis[from] + money[exps[to]];
vis[to] = true;
q.push({to});
}
}
}
return dis[n] - money[exps[n]];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
#include <bits/stdc++.h>
#define set(x, y) memset(x, y, sizeof x)
using namespace std;
using ll = long long;
const int inf = 0x7f7f7f7f;
const int N = 1e5 + 10;
const int M = 2e5 + 10;
int n, m, K, S;
ll money[2];
bool exps[N];
bool zombie[N];
int head[N];
ll dis[N];
int pt = 1;
struct Edge {
int to, next;
} edge[2 * M];
struct node {
int from;
bool operator<(const node &e) const {
return dis[from] > dis[e.from];
}
};
void add_edge(int from, int to) {
Edge &e = edge[pt];
e.to = to;
e.next = head[from];
head[from] = pt;
pt++;
}
bool vis[N];
ll min_cost() {
set(dis, inf);
dis[1] = 0;
priority_queue<node> q;
q.push({1});
while(q.size()) {
int from = q.top().from;
vis[from] = true;
q.pop();
for(int i = head[from]; i; i = edge[i].next) {
int to = edge[i].to;
if(vis[to]) continue;
if(zombie[to]) continue;
if(dis[from] + money[exps[to]] < dis[to]) {
dis[to] = dis[from] + money[exps[to]];
vis[to] = true;
q.push({to});
}
}
}
return dis[n] - money[exps[n]];
}
void mark(int x) {
auto q = queue<pair<int, int>>();
q.push({x, 0});
vis[x] = true;
while(q.size()) {
auto n = q.front();
q.pop();
exps[n.first] = true;
if(n.second < S) {
for(int i = head[n.first]; i; i = edge[i].next) {
int to = edge[i].to;
if(vis[to]) continue;
vis[to] = true;
q.push({to, n.second + 1});
}
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("diyi.in", "r", stdin);
freopen("diyi.out", "w", stdout);
#endif
cin >> n >> m >> K >> S;
cin >> money[0] >> money[1];
int t1, t2;
for(int i = 0; i < K; i++) {
cin >> t1;
zombie[t1] = true;
}
for(int i = 0; i < m; i++) {
cin >> t1 >> t2;
add_edge(t1, t2);
add_edge(t2, t1);
}
for(int i = 1; i <= n; i++) {
if(zombie[i]) {
mark(i);
set(vis, 0);
}
}
cout << min_cost() << endl;
return 0;
}
|