题解

2 条题解

  • 1
    @ 2017-10-30 16:10:24

    这道题我是拿状压做的,虽然慢了点(#滑稽)
     因为m<=20,且1,m,不受限制所以可以说m<=18这样状压就妥妥的了。我们完全可以先预处理出来在那些点能用的情况下1~m的最短路,然后将所有可行解建一个链表,缩短时间,然后再算出来每一天那些码头不能用,然后传统DP就好了。

    #include<iostream>
    #include<cstdlib>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<map>
    #include<queue>
    #include<string>
    #include<cmath>
    using namespace std;
    int t,n,m,k,zz,d;
    struct ro{
        int to,l;
        int next;
    }road[1000];
    int a[40];
    void build(int x,int y,int z){
        zz++;
        road[zz].to=y;
        road[zz].next=a[x];
        road[zz].l=z;
        a[x]=zz;
    }
    int dis[(1<<18)+5][21];
    int q[200],zt[105],head,en;
    bool rd[200];
    bool yx;
    int pre[(1<<18)+5];
    bool spfa(int tt){
        memset(q,0,sizeof(q));
        head=1,en=0;
        dis[tt][1]=0;
        rd[1]=1;
        en++;
        q[en]=1;
        while(en>=head)
        {
            int x=q[head];
            head++;
            rd[x]=0;
            for(int i=a[x];i>0;i=road[i].next)
            {
             
                int y=road[i].to;
                if(y==n||(1<<(y-2)&tt))
                {
                    if(dis[tt][y]>dis[tt][x]+road[i].l)
                    {
                        dis[tt][y]=dis[tt][x]+road[i].l;
                        if(!rd[y])
                        {
                            rd[y]=1;
                            en++;
                            q[en]=y;
                        }
                    }
                }
            }
        }
        if(dis[tt][n]!=dis[tt][0])
            return 1;
        return 0;
    }
    int f[2][(1<<18)+5];
    int main(){
        memset(pre,-1,sizeof(pre));
        memset(dis,0x3f,sizeof(dis));
        scanf("%d%d%d%d",&t,&n,&k,&m);
        for(int i=1;i<=m;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            build(x,y,z);
            build(y,x,z);
        }
        int lla=0;;
        for(int i=0;i<(1<<(n-2));i++)
        {
            if(spfa(i))
            {
                if(i==0) yx=1;
                pre[lla]=i;
                lla=i;
            }
        }
        scanf("%d",&d);
        for(int i=1;i<=d;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            for(int j=y;j<=z;j++)
                zt[j]|=(1<<(x-2));
        }
        int la=1,now=0,mn=-k;
        for(int i=1;i<=t;i++)
        {
            swap(la,now);
            int mn2=0x7fffffff;
            for(int j=0;j!=-1;j=pre[j])
            {
                if((j&zt[i])||((!yx)&&j==0)) continue;
                if(f[la][j])
                {
                    f[now][j]=min(f[la][j]+dis[j][n],mn+k+dis[j][n]);
                    mn2=min(mn2,f[now][j]);
                }
                else
                {
                    f[now][j]=mn+k+dis[j][n];
                    mn2=min(mn2,f[now][j]);
                }
            }
            memset(f[la],0,sizeof(f[la]));
            mn=mn2;
        }
        printf("%d\n",mn);
        //while(1);
        return 0;
    }
    
  • 0
    @ 2018-01-21 10:32:04

    WA*n
    于是拿vijos试水保ac率
    应该在填表的时候先初始化f[i]=t[1][i] 就不用在最后-K了
    先用最短路预处理 然后dp
    t[i][j]表示i~j天只走一条最短路的花销
    f[i]表示到第i天的最少花销
    边界f[0]=0 f[i]=t[1][i]
    然后f[i]=min(f[i],f[j]+t[j+1][i]+K) K为换路的费用 0<=j

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    using namespace std;
    int n, m, K, E,d;
    struct edge {
        int v, nxt,w;
    }e[801];    //n*n*2 无向图
    int p[21], eid=0;
    long long dist[21], t[101][101],f[101];     //t表示i~j天都走同一路线的最短路
    inline void ins(int u,int v,int w) {
        eid++; e[eid].v = v; e[eid].w = w; e[eid].nxt = p[u]; p[u] = eid;
    }
    inline void ins2(int u, int v, int w) {
        ins(u, v, w); ins(v, u, w);
    }
    inline int read() {
        int x; scanf("%d", &x); return x;
    }
    
    bool ava[21],book[101][21];
    void spfa() {
        bool inq[21];
        queue<int> q;
        //memset(ava, true, sizeof(ava));
        memset(dist, 0x3f, sizeof(dist));
        memset(inq, false, sizeof(inq));
        q.push(1); inq[1] = true;
        dist[1] = 0;
        while (!q.empty()) {                        //预处理每个时刻的最短路
            int u = q.front();
            q.pop();
            int v;
            inq[u] = false;
            for (int i = p[u]; i; i = e[i].nxt) {
                v = e[i].v;
                if(ava[v])
                    if (dist[u] + e[i].w < dist[v])
                    {
                        dist[v] = dist[u] + e[i].w;
                        if (!inq[v]) {
                            inq[v] = 1; q.push(v);
                        }
                    }
            }
        }
    }
    
    void solve() {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                memset(ava, true, sizeof(ava));
                for(int k=1;k<=m;k++)
                    for(int l=i;l<=j;l++)
                        if(!book[l][k]) //第l天k不能用
                        {
                            ava[k] = false;
                            break;
                        }
                spfa();
                dist[m] >= 0x3f ? t[i][j] = dist[m] : t[i][j] = dist[m] * (j - i + 1);
            }
        memset(f, 0x3f, sizeof(f));
        f[0] = 0;
        for (int i = 1; i <= n; i++)        //处理每一天
        {
            f[i] = t[1][i];
            for (int j = 0; j < i; j++) {       //前j-1天的最小花销+j~i天的最短路之和+K(换路花销)
                f[i] = min(f[i], f[j] + t[j + 1][i] + K);
            }
        }
    }
    int main() {
        scanf("%d%d%d%d", &n, &m, &K, &E);
        memset(book, true, sizeof(book));
        for (int i = 1; i <= E; i++)
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            ins2(x, y, z);
        }
        scanf("%d", &d);
        for (int i = 0; i < d; i++)
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            for (int j = y; j <= z; j++)
                book[j][x] = false; //标记是否可用
        }
        solve();
        cout <<f[n];
        //system("pause");
        return 0;
    }
    
  • 1

信息

难度
4
分类
(无)
标签
递交数
134
已通过
52
通过率
39%
被复制
1
上传者