DZY 's BLOG - Hello World!

BZOJ2763: [JLOI2011]飞行路线【分层图dijkstra+堆】

这道题也是分层图。k次机会让边权变0。虽然以前搞过但是好久了我也忘了。于是写死写死地写。然后纠结了下标纠结了n久之后就过了。

BZOJ2763
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	`#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` `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=r10+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=getint(),e=getint();` `for(int` `i=1;i<=m;i++)a=getint(),b=getint(),c=getint(),ae(a,b,c),ae(b,a,c);` `for(int` `k=1;k<=K;k++)` `for(int` `i=0;i<n;i++)` `for(int` `j=h[i];~j;j=n1[j]){` `ae(i+nk,p[j]+nk,w[j]);` `ae(i+(k-1)n,nk+p[j],0);` `}dijkstra(s);` `printf("%d\n",d[nK+e]);` `return` `0;` `}`