首页 > 代码库 > 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