bzoj1003 物流运输

谁践踏了优雅 2021-10-30 02:18 340阅读 0赞

[bzoj1003 物流运输][bzoj1003]

设cost\[i\]\[j\]为第i天到第j天，不经过这些天关闭的所有港口（指在这一段时间不是每天都能过）的最短路，

设f\[i\]为前i天最短路，则f\[i\]=min(f\[i\] , f\[j\]+cost\[j+1\]\[i\]\*(i-j)+k)

因为对第一天多加了一个k，最后减去即可。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<vector>
    #include<queue>
    #define LL long long
    #define int LL
    #define INF 0x7fffffff
    #define ma(x) memset(x,0,sizeof(x))
    using namespace std;
    struct edge
    {
        int u,v,w,nxt;
        #define u(x) ed[x].u
        #define v(x) ed[x].v
        #define w(x) ed[x].w
        #define n(x) ed[x].nxt
    }ed[2000];
    int first[25],num_e;
    #define f(x) first[x]
    int n,m,k,e;
    int d,p[1000],a[1000],b[1000];
    vector<int> inc[110]; 
    int dis[25];bool v[25];
    void dijkstra(int s)
    {
        for(int i=1;i<=m;i++)dis[i]=INF;
        priority_queue<pair<int,int> >q;
        dis[s]=0;
        q.push(make_pair(0,s));
        while(q.size())
        {
            int x=q.top().second;q.pop();
            if(v[x])continue;
            v[x]=1;
            for(int i=f(x);i;i=n(i))
                if(dis[v(i)]>dis[x]+w(i))
                dis[v(i)]=dis[x]+w(i),
                q.push(make_pair(-dis[v(i)],v(i)));
        }
    }
    int f[110],cost[110][110];
    inline void add(int u,int v,int w);
    signed main()
    {
    //    freopen("in.txt","r",stdin);
    
        scanf("%lld%lld%lld%lld",&n,&m,&k,&e);
        for(int i=1;i<=e;i++)
        {
            int u,v,w;
            scanf("%lld%lld%lld",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        scanf("%lld",&d);
        for(int i=1;i<=d;i++)
        {
            scanf("%lld%lld%lld",&p[i],&a[i],&b[i]);
            for(int j=a[i];j<=b[i];j++)
                inc[j].push_back(p[i]);
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=i;j++)
            {
                ma(v);
                for(int k=j;k<=i;k++)
                    for(int l=0;l<inc[k].size();l++)v[inc[k][l]]=1;
                dijkstra(1);
                cost[j][i]=dis[m];
            }
        for(int i=1;i<=n;i++)f[i]=INF;
        for(int i=1;i<=n;i++)
            for(int j=0;j<i;j++)
                f[i]=min(f[i],f[j]+cost[j+1][i]*(i-j)+k);
        printf("%lld\n",f[n]-k);
    }
    inline void add(int u,int v,int w)
    {
        ++num_e;
        u(num_e)=u;
        v(num_e)=v;
        w(num_e)=w;
        n(num_e)=f(u);
        f(u)=num_e;
    }

转载于:https://www.cnblogs.com/Al-Ca/p/11179293.html

[bzoj1003]: https://loj.ac/problem/2311
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211029/ff08c15f3b634d33ad010017ef6cb16d.png