8
22
2015
0

[BZOJ1003] [ZJOI2006] 物流运输trans

前几天ygp就说了,是dp+spfa,然而我居然难以理解……

看着神犇们速A这题,我不禁感到太弱了……

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int en,n,m,K,E,d[105],h[105],D[105],P,dis[105][105],f[105],dp[105];

struct Edge{
int b,v,next;
}e[40005];

struct Closed{
int p,a,b;
}close[105];

void Yuchuli(int day1,int day2){
    memset(d,0,sizeof(d));
for(int i=0;i<P;i++){
    if(close[i].a>day2 || close[i].b<day1)continue;
    d[close[i].p]=1;
}
}

int spfa(){
memset(f,0,sizeof(f));
memset(D,0x3f,sizeof(D));
queue<int> Q;
Q.push(1);
f[1]=1;
D[1]=0;
int u,v;
while(!Q.empty()){
    u=Q.front();
    Q.pop();
    f[u]=0;
    for(int i=h[u];i;i=e[i].next){
        v=e[i].b;
        if(d[v])continue;
        if(D[u]+e[i].v<D[v]){
            D[v]=D[u]+e[i].v;
            if(!f[v]){
                Q.push(v);
                f[v]=1;
            }
        }
    }
}
return D[m];
}

void add(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}

int main(){
freopen("1003.in","r",stdin);
freopen("1003.out","w",stdout);
scanf("%d %d %d %d",&n,&m,&K,&E);
for(int i=0;i<E;i++){
    int sa,sb,sc;
    scanf("%d %d %d",&sa,&sb,&sc);
    add(sa,sb,sc);
    add(sb,sa,sc);
}
scanf("%d",&P);
for(int i=0;i<P;i++){
    scanf("%d %d %d",&close[i].p,&close[i].a,&close[i].b);
}
for(int i=1;i<=n;i++){
    for(int j=i;j<=n;j++){
        Yuchuli(i,j);
        dis[i][j]=spfa();
        if(dis[i][j]<0x3f3f3f3f)dis[i][j]*=j-i+1;
        //printf("%d\n",dis[i][j]);
    }
}
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++){
    for(int j=0;j<i;j++){
        dp[i]=min(dp[i],dp[j]+dis[j+1][i]+K);
    }
}
printf("%d\n",dp[n]-K);
return 0;
}

水平若,代码丑,速度慢,这就是3个特点。

orz wyx秒杀这题

Category: BZOJ | Tags: OI | Read Count: 560

登录 *


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

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