4
27
2016
0

[BZOJ3771] Triple

这题是FFT的应用

考虑构建指数型母函数，系数是物品的个数，指数是物品的价值

然后分成三种情况容斥一下

然后就不会了。。这怎么FFT啊

然后orz了Miskcoo大神的博客，不仅学会了怎么做，还优化了一下速度……

复数什么的直接无视，和正常的情况一样搞就行了

以后还是要多做题啊……

?
bzoj 3771
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
57
58
59
60
61
62
63
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;
 
const int N=262145;
const double Pi=acos(-1);
 
int An,n,Step,mx_val,Rev[N];
 
struct Complex{
double a,b;
Complex(){a=0.0,b=0.0;}
Complex(double sa,double sb){a=sa;b=sb;}
friend Complex operator+(Complex A,Complex B){return Complex(A.a+B.a,A.b+B.b);}
friend Complex operator-(Complex A,Complex B){return Complex(A.a-B.a,A.b-B.b);}
friend Complex operator*(Complex A,Complex B){return Complex(A.a*B.a-A.b*B.b,A.a*B.b+A.b*B.a);}
}A[N],B[N],C[N],div2=Complex(1.0/2.0,0.0),div3=Complex(1.0/3.0,0.0),div6=Complex(1.0/6.0,0.0);
 
void FFT(Complex *x,int flag){
for(int i=0;i<n;i++)if(i<Rev[i])swap(x[i],x[Rev[i]]);
for(int k=1;k<n;k<<=1){
    Complex wk=Complex(cos(Pi/k),flag*sin(Pi/k));
    for(int i=0;i<n;i+=k<<1){
        Complex wkj=Complex(1.0,0.0);
        for(int j=0;j<k;j++){
            Complex a=x[i+j],b=x[i+j+k]*wkj;
            x[i+j]=a+b;
            x[i+j+k]=a-b;
            wkj=wkj*wk;
        }
    }
}
if(flag==-1)for(int i=0;i<n;i++)x[i].a/=n;
}
 
int main(){
freopen("3771.in","r",stdin);
freopen("3771.out","w",stdout);
scanf("%d",&An);
for(int i=0;i<An;i++){
    int x;
    scanf("%d",&x);
    A[x].a+=1.0;
    B[x*2].a+=1.0;
    C[x*3].a+=1.0;
    if(3*x>mx_val)mx_val=3*x;
}
for(n=1,Step=0;n<mx_val;n<<=1,Step++);
for(int i=0;i<n;i++)Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Step-1));
FFT(A,1);
FFT(B,1);
for(int i=0;i<n;i++)A[i]=A[i]*A[i]*A[i]*div6+(A[i]*(A[i]-B[i])-B[i])*div2+A[i];
FFT(A,-1);
for(int i=1;i<mx_val;i++)A[i]=A[i]+C[i]*div3;
for(int i=0;i<mx_val;i++){
    int x=(int)(A[i].a+0.5);
    if(x)printf("%d %d\n",i,x);
}
return 0;
}

 

Category: BZOJ | Tags: OI bzoj
4
26
2016
0

[BZOJ4246] 两个人的星座

考虑暴力求解

先枚举第一个点，把剩下的点全部扔到一个数组里面

然后极角排序，每次选择一个点和之前枚举的点作为这两个三角形中的两个点，然后乘法计数原理就可以了

注意需要对上面和下面各做一遍(因为两个点上下都有可能)

注意这样做会出现重复，具体就是枚举两个点重复一次和中间计算时上下各计算一次一共四次重复，所以总答案除以4就好了

?
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
  
const int N=3005;
const double Pi=acos(-1);
  
int n,Top,cnt[2][3],test[N];
long long ans;
  
struct Point{
int x,y;
Point(){}
Point(int sa,int sb){x=sa;y=sb;}
friend Point operator+(Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
friend Point operator-(Point A,Point B){return Point(A.x-B.x,A.y-B.y);}
}O;
  
double Atan(Point A){double x=atan2(A.y,A.x);return x>0?x:x+Pi;}
  
pair<Point,int> poi[N],St[N],St2[N];
pair<double,int> Stab[N];
  
void Cal(int col){
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=Top;i++)Stab[i]=make_pair(Atan(St[i].first-O),i);
sort(Stab+1,Stab+Top+1);
for(int i=1;i<=Top;i++)St2[i]=St[Stab[i].second];
for(int i=1;i<=Top;i++)St[i]=St2[i];
for(int i=1;i<=Top;i++){
    if(St[i].first.y<O.y || St[i].first.y==O.y && St[i].first.x>O.x)cnt[test[i]=0][St[i].second]++;
    else cnt[test[i]=1][St[i].second]++;
}
for(int i=1;i<=Top;i++){
    cnt[test[i]][St[i].second]--;
    int CanDoneFirst=1,CanDoneSecond=1;
    if(col!=0)CanDoneFirst*=cnt[0][0];
    if(col!=1)CanDoneFirst*=cnt[0][1];
    if(col!=2)CanDoneFirst*=cnt[0][2];
    if(St[i].second!=0)CanDoneSecond*=cnt[1][0];
    if(St[i].second!=1)CanDoneSecond*=cnt[1][1];
    if(St[i].second!=2)CanDoneSecond*=cnt[1][2];
    ans+=(long long)CanDoneFirst*CanDoneSecond;
    CanDoneFirst=1,CanDoneSecond=1;
    if(col!=0)CanDoneFirst*=cnt[1][0];
    if(col!=1)CanDoneFirst*=cnt[1][1];
    if(col!=2)CanDoneFirst*=cnt[1][2];
    if(St[i].second!=0)CanDoneSecond*=cnt[0][0];
    if(St[i].second!=1)CanDoneSecond*=cnt[0][1];
    if(St[i].second!=2)CanDoneSecond*=cnt[0][2];
    ans+=(long long)CanDoneFirst*CanDoneSecond;
    cnt[test[i]^=1][St[i].second]++;
}
}
  
int main(){
freopen("4246.in","r",stdin);
freopen("4246.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%d %d %d",&poi[i].first.x,&poi[i].first.y,&poi[i].second);
}
for(int i=1;i<=n;i++){
    Top=0;
    for(int j=1;j<=n;j++)if(i!=j)St[++Top]=poi[j];
    O=poi[i].first;
    Cal(poi[i].second);
}
printf("%lld\n",ans/4);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
26
2016
0

[BZOJ1717] [Usaco2006 Dec]Milk Patterns 产奶的模式

二分+后缀数组

对于height分块然后二分判定就可以了

?
bzoj 1717
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const int N=20005;
 
int sa[N],rank[N],rank2[N],n,height[N],wa[N],ws[N],a[N],k;
 
bool cmp(int *r,int a,int b,int l){return (r[a]==r[b])&(r[a+l]==r[b+l]);}
 
void GetSA(int *r,int *sa,int n,int m){
int i,j,p,*x=rank,*y=rank2,*t;
for(i=0;i<m;i++)ws[i]=0;
for(i=0;i<n;i++)ws[x[i]=r[i]]++;
for(i=1;i<m;i++)ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--){sa[--ws[x[i]]]=i;}
for(j=p=1;p<n;j*=2,m=p){
    for(p=0,i=n-j;i<n;i++)y[p++]=i;
    for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
    for(i=0;i<m;i++)ws[i]=0;
    for(i=0;i<n;i++)ws[wa[i]=x[y[i]]]++;
    for(i=1;i<m;i++)ws[i]+=ws[i-1];
    for(i=n-1;i>=0;i--)sa[--ws[wa[i]]]=y[i];
    for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
 
void CalHeight(int *r,int *sa,int n){
int i,j,k=0;
for(i=1;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k){
    for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}
}
 
bool Check(int x){
int cnt,i=2;
while(1){
    while(i<=n && height[i]<x)i++;
    if(i>n)break;
    cnt=1;
    while(i<=n && height[i]>=x){cnt++;i++;}
    if(cnt>=k)return 1;
}
return 0;
}
 
int Div2(){
int l=1,r=n,ans=1;
while(l<=r){
    int mid=l+r>>1;
    if(Check(mid)){ans=mid;l=mid+1;}
    else r=mid-1;
}
return ans;
}
 
int main(){
freopen("1717.in","r",stdin);
freopen("1717.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
a[n]=0;
GetSA(a,sa,n+1,N-4);
CalHeight(a,sa,n);
printf("%d\n",Div2());
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
26
2016
0

[BZOJ1113] [Poi2008]海报PLA

简单的单调栈

?
bzoj 1113
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
int n,Stack[250005],Top,ans;
 
int main(){
freopen("1113.in","r",stdin);
freopen("1113.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    int x,y;
    scanf("%d %d",&x,&y);
    while(Top && Stack[Top]>=y){if(Stack[Top]!=y)ans++;Top--;}
    Stack[++Top]=y;
}
printf("%d\n",ans+Top);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
25
2016
0

[BZOJ1086] [SCOI2005]王室联邦

树上分块

对于每个子树维护siz

大于B就把这个子树和当前的省作为一块丢掉（这一块一定小于2*B,否则一定会在这个子树的内部再分块）

最后剩下的点在下面找一个子树丢进去就行了,必定满足条件

?
bzoj 1086
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
57
58
59
60
61
62
63
64
65
66
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const int N=2005;
 
int n,B,en,h[N],St[N],belong[N],St_size,siz[N],home[N],hcnt;
 
struct Edge{
int b,next;
}e[N];
 
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
 
void DFS(int u,int fa){
St[++St_size]=u;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==fa)continue;
    DFS(v,u);
    if(siz[u]+siz[v]>=B){
        siz[u]=0;
        home[++hcnt]=u;
        while(St[St_size]!=u)belong[St[St_size--]]=hcnt;
    }
    else siz[u]+=siz[v];
}
siz[u]++;
}
 
void Paint(int u,int fa,int col){
if(!belong[u])belong[u]=col;
else col=belong[u];
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa)Paint(v,u,col);
}
}
 
int main(){
freopen("1086.in","r",stdin);
freopen("1086.out","w",stdout);
scanf("%d %d",&n,&B);
if(n<B){puts("0");return 0;}
for(int i=1;i<n;i++){
    int u,v;
    scanf("%d %d",&u,&v);
    AddEdge(u,v);
    AddEdge(v,u);
}
DFS(1,0);
if(!hcnt)home[++hcnt]=1;
Paint(1,0,hcnt);
printf("%d\n",hcnt);
for(int i=1;i<=n;i++)printf("%d ",belong[i]);
putchar('\n');
for(int i=1;i<=hcnt;i++)printf("%d ",home[i]);
putchar('\n');
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
25
2016
0

[BZOJ2194] 快速傅立叶之二

把FFT模版略微改动一下

?
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
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
  
const int N=270000;
const double Pi=acos(-1);
  
int An,Bn,Cn,n,Rev[N],Step;
  
struct Complex{
double a,b;
Complex(){}
Complex(double sa,double sb){a=sa;b=sb;}
friend Complex operator+(Complex A,Complex B){return Complex(A.a+B.a,A.b+B.b);}
friend Complex operator-(Complex A,Complex B){return Complex(A.a-B.a,A.b-B.b);}
friend Complex operator*(Complex A,Complex B){return Complex(A.a*B.a-A.b*B.b,A.a*B.b+A.b*B.a);}
}A[N],B[N],C[N];
  
void FFT(Complex *x,int flag){
for(int i=0;i<n;i++)if(i<Rev[i])swap(x[i],x[Rev[i]]);
for(int k=1;k<n;k<<=1){
    Complex wk=Complex(cos(Pi/k),flag*sin(Pi/k));
    for(int i=0;i<n;i+=k<<1){
        Complex wkj=Complex(1.0,0.0);
        for(int j=0;j<k;j++){
            Complex a=x[i+j],b=x[i+j+k]*wkj;
            x[i+j]=a+b;
            x[i+j+k]=a-b;
            wkj=wkj*wk;
        }
    }
}
if(flag==-1)for(int i=0;i<n;i++)x[i].a/=n;
}
  
int main(){
freopen("2194.in","r",stdin);
freopen("2194.out","w",stdout);
scanf("%d",&An);
Bn=An;Cn=An+Bn-1;
for(int i=0;i<An;i++)scanf("%lf %lf",&A[i].a,&B[An-i].a);
for(n=1,Step=0;n<Cn;n<<=1,Step++);
for(int i=0;i<n;i++)Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Step-1));
FFT(A,1);FFT(B,1);
for(int i=0;i<n;i++)C[i]=A[i]*B[i];
FFT(C,-1);
for(int i=Cn/2+1;i<=Cn;i++)printf("%d\n",(int)(C[i].a+0.5));
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
23
2016
0

[BZOJ2049] [Sdoi2008]Cave 洞穴勘测

LCT

?
bzoj 2049
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<cstdio>
#include<algorithm>
using namespace std;
 
int n,m;
 
struct Node{
int rev;
Node *ch[2],*fa;
Node(Node *fat);
void Pushdown();
}*root[10005],*Null;
 
Node::Node(Node *fat){
fa=fat;
ch[0]=ch[1]=Null;
rev=0;
}
 
void Node::Pushdown(){
if(rev){
    if(ch[0]!=Null)ch[0]->rev^=1;
    if(ch[1]!=Null)ch[1]->rev^=1;
    swap(ch[0],ch[1]);
    rev=0;
}
}
 
int Notroot(Node *x){
return (x->fa->ch[0]==x)||(x->fa->ch[1]==x);
}
 
void Prepare(Node *x){
if(Notroot(x))Prepare(x->fa);
x->Pushdown();
}
 
void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
}
 
void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
    Node *y=x->fa,*z=y->fa;
    if(!Notroot(y))Rotate(x,y->ch[0]==x);
    else {
        if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
        else if(y->ch[1]==x && z->ch[1]==y){Rotate(y,0);Rotate(x,0);}
        else if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
        else {Rotate(x,0);Rotate(x,1);}
    }
}
}
 
void Access(Node *x){
for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;}
}
 
void Makeroot(Node *x){
Access(x);
Splay(x);
x->rev^=1;
}
 
void Link(Node *u,Node *v){
Makeroot(u);
u->fa=v;
}
 
void Cut(Node *u,Node *v){
Makeroot(u);
Access(v);
Splay(v);
if(v->ch[0]==u){v->ch[0]=Null;u->fa=Null;}
}
 
Node *Find(Node *x){
Access(x);
Splay(x);
while(x->ch[0]!=Null)x=x->ch[0];
return x;
}
 
Node *GetNull(){
Node *p=new Node(Null);
p->ch[0]=p->ch[1]=p->fa=p;
p->rev=0;
return p;
}
 
Node *ToLct(int x){
return root[x];
}
 
int main(){
freopen("2049.in","r",stdin);
freopen("2049.out","w",stdout);
scanf("%d %d",&n,&m);
Null=GetNull();
for(int i=1;i<=n;i++)root[i]=new Node(Null);
for(int i=1;i<=m;i++){
    int u,v;
    char s[10];
    scanf("%s %d %d",s,&u,&v);
    if(s[0]=='C')Link(ToLct(u),ToLct(v));
    if(s[0]=='D')Cut(ToLct(u),ToLct(v));
    if(s[0]=='Q'){
        if(Find(ToLct(u))==Find(ToLct(v)))puts("Yes");
        else puts("No");
    }
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
23
2016
0

[BZOJ2662] [BeiJing wc2012]冻结

水题可以愉悦身心

分层图SPFA

?
bzoj 2662
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
 
int n,m,k,en,h[55],D[55][55],flag[55][55],ans;
 
struct Que{
int a,b;
Que(int sa,int sb){a=sa;b=sb;}
};
 
queue<Que> Q;
 
struct Edge{
int b,v,next;
}e[2005];
 
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
 
void SPFA(){
memset(D,127,sizeof(D));
flag[0][1]=1;
D[0][1]=0;
Q.push(Que(0,1));
while(!Q.empty()){
    Que u=Q.front();
    Q.pop();
    flag[u.a][u.b]=0;
    for(int i=h[u.b];i;i=e[i].next){
        int v=e[i].b;
        if(D[u.a][v]>D[u.a][u.b]+e[i].v){
            D[u.a][v]=D[u.a][u.b]+e[i].v;
            if(!flag[u.a][v]){
                flag[u.a][v]=1;
                Q.push(Que(u.a,v));
            }
        }
    }
    if(u.a<k){
        for(int i=h[u.b];i;i=e[i].next){
            int v=e[i].b;
            if(D[u.a+1][v]>D[u.a][u.b]+e[i].v/2){
                D[u.a+1][v]=D[u.a][u.b]+e[i].v/2;
                if(!flag[u.a+1][v]){
                    flag[u.a+1][v]=1;
                    Q.push(Que(u.a+1,v));
                }
            }
        }
    }
}
ans=D[0][n];
for(int i=1;i<=k;i++)ans=min(ans,D[i][n]);
}
 
int main(){
freopen("2662.in","r",stdin);
freopen("2662.out","w",stdout);
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=m;i++){
    int u,v,w;
    scanf("%d %d %d",&u,&v,&w);
    AddEdge(u,v,w);
    AddEdge(v,u,w);
}
SPFA();
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
23
2016
0

[BZOJ2761] [JLOI2011]不重复数字

行尾有空格会PE

真是日了狗了

?
bzoj 2761
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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
int n,T;
 
struct Data{
int id,x;
friend bool operator<(Data A,Data B){return A.id<B.id;}
}a[50005];
 
bool cmp(Data A,Data B){return A.x<B.x || (A.x==B.x && A.id<B.id);}
 
int main(){
freopen("2761.in","r",stdin);
freopen("2761.out","w",stdout);
scanf("%d",&T);
while(T--){
    scanf("%d",&n);
    a[n+1].id=99999;
    for(int i=1;i<=n;i++)scanf("%d",&a[i].x),a[i].id=i;
    sort(a+1,a+n+1,cmp);
    for(int i=2;i<=n;i++)if(a[i].x==a[i-1].x)a[i].id=99999;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){if(a[i+1].id==99999){printf("%d\n",a[i].x);break;}else printf("%d ",a[i].x);}
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
22
2016
0

[BZOJ2763] [JLOI2011]飞行路线

分层图SPFA

最后必须依次比较，因为可能因为边数太少用不到k次

?
bzoj 2763
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
 
int n,m,k,S,T,en,h[10005],D[15][10005],flag[15][10005],ans;
 
struct Que{
int a,b;
Que(int sa,int sb){a=sa;b=sb;}
};
 
queue<Que> Q;
 
struct Edge{
int b,v,next;
}e[100005];
 
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
 
void SPFA(){
memset(D,127,sizeof(D));
D[0][S]=0;
flag[0][S]=1;
Q.push(Que(0,S));
while(!Q.empty()){
    Que u=Q.front();
    Q.pop();
    flag[u.a][u.b]=0;
    for(int i=h[u.b];i;i=e[i].next){
        int v=e[i].b;
        if(D[u.a][v]>D[u.a][u.b]+e[i].v){
            D[u.a][v]=D[u.a][u.b]+e[i].v;
            if(!flag[u.a][v]){
                flag[u.a][v]=1;
                Q.push(Que(u.a,v));
            }
        }
    }
    if(u.a<k){
        for(int i=h[u.b];i;i=e[i].next){
            int v=e[i].b;
            if(D[u.a+1][v]>D[u.a][u.b]){
                D[u.a+1][v]=D[u.a][u.b];
                if(!flag[u.a+1][v]){
                    flag[u.a+1][v]=1;
                    Q.push(Que(u.a+1,v));
                }
            }
        }
    }
}
ans=D[0][T];
for(int i=1;i<=k;i++){ans=min(ans,D[i][T]);}
}
 
int main(){
freopen("2763.in","r",stdin);
freopen("2763.out","w",stdout);
scanf("%d %d %d %d %d",&n,&m,&k,&S,&T);
for(int i=1;i<=m;i++){
    int u,v,w;
    scanf("%d %d %d",&u,&v,&w);
    AddEdge(u,v,w);
    AddEdge(v,u,w);
}
SPFA();
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com