LGOJ P3393 | 逃离僵尸岛

Portal

​题目只有两个步骤:处理每个点的点权;跑一遍点权最短路。

​对于 KK 个城市,可以考虑把点权赋为 \infty 。对于 KK 个点周围的点,可以 bfs 进行预处理。但当 KK 较大时,复杂度为 O(kN)O(kN), 与队列优化的 Bellman ford 相同。可以考虑虚点优化,先新建一个编号为 n+1n+1 的点,再从这个点向 KK 个点连单向边,最后从 n+1n+1 号点开始 bfs 即可。题目点权不大,可以考虑让每条边的边权等于连接的两个顶点的点权之和,然后跑一遍 Dijkstra,将边权最短路除以 2 即为点权最短路。

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
#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
typedef long long ll;
typedef std::pair<ll,int> node;
const int _=1e5+233,__=(_<<2)+_;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,m,k,s,fp=1,P,Q,z[_],hed[_],ver[__],nxt[__];ll p[_],d[_],edg[__];
int read() {
int x=0;char c=getchar();
while(c<48||c>57) c=getchar();
while(c>47&&c<58) {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x;
}
void link(int u,int v) {
ver[++fp]=v;nxt[fp]=hed[u];hed[u]=fp;
ver[++fp]=u;nxt[fp]=hed[v];hed[v]=fp;
}
void lin_toto(int u,int v) {
ver[++fp]=v;nxt[fp]=hed[u];hed[u]=fp;
}
void bfs() {
std::queue<int> q;q.push(n+1);int u,v,dep[_]={};
while(q.size()){
u=q.front();q.pop();
for(int i=hed[u];i;i=nxt[i])
if(!dep[v=ver[i]]){
dep[v]=dep[u]+1;q.push(v);
if(!p[v]) {if(dep[v]<=s) p[v]=Q;else p[v]=P;}
}
}
}
void dijkstra() {
std::priority_queue<node> heap;heap.push((node){0,1});
int u,v,vis[_]={};ll w;memset(d,0x3f,sizeof(d));d[1]=0;
while(heap.size()){
u=heap.top().second;heap.pop();if(vis[u]) continue;vis[u]=1;
for(int i=hed[u];i;i=nxt[i])
if(d[v=ver[i]]>d[u]+(w=edg[i])) heap.push((node){-(d[v]=d[u]+w),v});
}
}
int main() {
n=read(),m=read(),k=read(),s=read(),P=read(),Q=read();++s;
for(int i=0;i<k;++i) p[z[i]=read()]=inf;
for(int i=0;i<m;++i) link(read(),read());
for(int i=0;i<k;++i) lin_toto(n+1,z[i]);
bfs();p[1]=p[n]=0;
for(int i=2;i<=(m<<1)+1;++i) edg[i]=p[ver[i]]+p[ver[i^1]];
dijkstra();
printf("%lld",d[n]>>1);
return 0;
}

Download

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

题解 OI

评论

您需要成为穿墙的邪仙以加载 Disqus。