首页 > 代码库 > 9.2.2
9.2.2
//// main.cpp// luogu9.2.2//// Created by Candy on 9/24/16.// Copyright © 2016 Candy. All rights reserved.//#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>using namespace std;const int N=1e5+5,M=2e5+5,INF=1e9;int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}struct edge{ int v,w,ne;}e[(M<<1)+N];int h[N<<1],cnt=0;void ins(int u,int v,int w){ cnt++; e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt; cnt++; e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;}int n,m,k,s,p,qq,tmp,u[M],v[M];int g[N],c[N],lst[N],num=0;//danger cengvoid dfs(int u,int d){//printf("dfs %d %d\n",u,d); if(d==0) return; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v;//printf("v %d\n",v); c[v]=d-1; g[v]=1; if(c[v]>=d-1) continue; dfs(v,d-1); }}void build(){ cnt=0;memset(h,0,sizeof(h)); ins(1,1+n,0);ins(n,n+n,0); for(int i=2;i<=n-1;i++){ if(g[i]) ins(i,i+n,qq); else ins(i,i+n,p); } for(int i=1;i<=m;i++){ ins(u[i]+n,v[i],0); ins(v[i]+n,u[i],0); }}struct hn{ int u,d; bool operator <(const hn &rhs)const{return d>rhs.d;}};int d[N],done[N];priority_queue<hn> q;void dijkstra(int s){ for(int i=1;i<=n<<1;i++) d[i]=INF; d[s]=0;q.push((hn){s,0}); while(!q.empty()){ hn x=q.top();q.pop(); int u=x.u; if(done[u]) continue; done[u]=1; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(d[v]>d[u]+e[i].w){ d[v]=d[u]+e[i].w; q.push((hn){v,d[v]}); } } }}int main(int argc, const char * argv[]) { n=read();m=read();k=read();s=read(); p=read();qq=read(); for(int i=1;i<=k;i++){ tmp=read();lst[++num]=tmp;g[tmp]=1;c[tmp]=s; } for(int i=1;i<=m;i++){ u[i]=read();v[i]=read();ins(u[i],v[i],0); } for(int i=1;i<=k;i++) dfs(lst[i],s); build(); dijkstra(1); for(int i=1;i<=n<<1;i++) printf("d %d\n",d[i]); printf("%d",d[n+n]); return 0;}
9.2.2
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。