BZOJ2662: [BeiJing wc2012]冻结【分层图dijkstra】

dzy posted @ 2013年6月13日 23:15 in BZOJ with tags BZOJ 分层图 dijkstra , 1788 阅读

n个顶点m条边。给你k次机会让边权减半。一次机会对一条边只能做一次。

n、k都是小于50，那么分层。然后就好了。有些细节比较纠结。于是调了好久。囧。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=300000;
const int maxm=7000000;
const int inf=1061109567;
struct HN{
    int x,dis; HN(){}; HN(int _x,int _d):x(_x),dis(_d){};
    inline bool operator < (HN b)const{ return dis<b.dis;}
}H[maxn]; int pos[maxn]={0},size=0; char buf[5000000],*pt=buf; 
int g[55][55]={0},hh[maxn],h[maxn],p[maxm],w[maxm],n1[maxm],d[maxn],vis[maxn]={0},tot=0,n,m,K;
inline int getint(){    int r=0;while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline void sw(int a,int b){
    pos[H[a].x]=b;pos[H[b].x]=a;
    swap(H[a],H[b]);
}void up(int x){
    if(x==1) return;
    if(H[x]<H[x>>1]) sw(x,x>>1),up(x>>1);
}void down(int x){
    int son=x;   if((x<<1)<=size&&H[x<<1]<H[x]) son=x<<1;
    if((x<<1|1)<=size&&H[x<<1|1]<H[son]) son=x<<1|1;
    if(son!=x) sw(x,son),down(son);
}void del(int x){
    sw(x,size); size--; up(x); down(x);
}void ins(HN hn){
    H[++size]=hn; pos[hn.x]=size; up(size);
}inline void ae(int a,int b,int c){
    p[tot]=b; w[tot]=c; n1[tot]=h[a]; h[a]=tot++;
}int dijkstra(int s){
    HN S(s,0),o,tmp;
    size=d[s]=0; ins(S);
    while(size){
        o=H[1]; pos[H[1].x]=0; del(1); //if(o.x==e) return o.dis;
        if(vis[o.x]) continue; vis[o.x]=1;
        for(int i=h[o.x];~i;i=n1[i]) if(!vis[p[i]])
            if(o.dis+w[i]<d[p[i]]){
                d[p[i]]=o.dis+w[i];
                if(pos[p[i]]) {H[pos[p[i]]].dis=d[p[i]];up(pos[p[i]]);}
                else ins(HN(p[i],o.dis+w[i]));
            }
    }return -1;
}int main(){
    fread(pt,1,5000000,stdin); n=getint(); m=getint(); K=getint(); 
    memset(h,0xff,sizeof(h)); memset(d,63,sizeof(d));
    int a,b,c,s=1,e=n;
    for(int i=1;i<=m;i++)a=getint(),b=getint(),c=getint(),ae(a,b,c),ae(b,a,c);
    memcpy(hh,h,sizeof(h));
    for(int k=1;k<=K;k++) for(int i=1;i<=n;i++) for(int j=hh[i];~j;j=n1[j]){
        ae(i+n*k,p[j]+n*k,w[j]); 
        ae(i+(k-1)*n,n*k+p[j],w[j]>>1);
    }dijkstra(s); int An=inf; for(int i=0;i<=K;i++) An=min(An,d[n*i+e]);
    printf("%d\n",An); return 0;
}
Small_feed 评论 (16)
1
[回复]
Avatar_small
Digital Ali 说:
2021年9月16日 17:17 Hey, I am so thrilled I found your blog, I am here now and could just like to say thank for a tremendous post and all round interesting website. Please do keep up the great work. I cannot be without visiting your blog again and again. 123 movies
2
[回复]
Avatar_small
SEO 说:
2021年10月01日 03:35

You made such an interesting piece to read, giving every subject enlightenment for us to gain knowledge. Thanks for sharing the such information with us to read this... madhur satta

3
[回复]
Avatar_small
SEO 说:
2021年10月18日 04:23 I think this is an informative post and it is very useful and knowledgeable. therefore, I would like to thank you for the efforts you have made in writing this article. umrah package from dubai
4
[回复]
Avatar_small
SEO 说:
2021年11月05日 03:03

A very awesome blog post. We are really grateful for your blog post. You will find a lot of approaches after visiting your post. 오피아트

5
[回复]
Avatar_small
global news 说:
2023年1月31日 21:26

I wanted to leave a little comment to support you and wish you a good continuation. Wishing you the best of luck for all your blogging efforts.

6
[回复]
Avatar_small
global news 说:
2023年1月31日 21:26

I wanted to leave a little comment to support you and wish you a good continuation. Wishing you the best of luck for all your blogging efforts.

7
[回复]
Avatar_small
Cladder 说:
2023年2月05日 04:33

Actually I read it yesterday but I had some thoughts about it and today I wanted to read it again because it is very well written.

8
[回复]
Avatar_small
Ower Shelf 说:
2023年3月22日 04:38

this post give me lots of advise it is very useful for me.

9
[回复]
Avatar_small
Digitals Magazine 说:
2023年4月19日 08:28

I really love this website I learned a lot from this website Thanks

10
[回复]
Avatar_small
Front Door 说:
2023年6月05日 04:55

I went over this website and I believe you have a lot of wonderful information, saved to my bookmarks

11
[回复]
Avatar_small
model-paper.comcom 说:
2023年6月09日 17:08

Modelpapers works on giving out better service in different forms and we do not sell or giveaway your personal information other than public info giving out by you. We are very conscious about mail spam and we try to protect every email as model-paper.com much as possible. In certain cases your mail may be exposed to public.

12
[回复]
Avatar_small
Falcon Media Marketi 说:
2023年8月19日 04:45

I was very pleased to find this site.I wanted to thank you for this great read!! I definitely enjoy every little bit of it and I have you bookmarked to check out new stuff you post.

13
[回复]
Avatar_small
mg comet price 说:
2023年9月14日 05:09

I was very pleased to find this site.I wanted to thank you for this great read!! I definitely enjoying every little bit of it and I have you bookmarked to check out new stuff you post.

14
[回复]
Avatar_small
how2invest 说:
2023年9月24日 05:52

I was exceptionally satisfied to find this site.I needed to thank you for this extraordinary read!! I most certainly partaking in every single piece of it and I have you bookmarked to look at new stuff you post.

15
[回复]
Avatar_small
how2invest 说:
2023年10月29日 04:31

I was exceptionally satisfied to find this site.I needed to thank you for this extraordinary read!! I most certainly partaking in every single piece of it and I have you bookmarked to look at new stuff you post.

16
[回复]
Avatar_small
Podcast 说:
2023年11月05日 04:22

I’m happy to find so many useful info here in the post, thanks for sharing. I love the variety of content available on your website. I’ll bookmark your blog and take the feeds also!


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter