[ZJOI2006]物流运输

做法

SPFA+DP

思路

贪心显然不可取，考虑用动归。
令表示第天的最小花费，最后输出的答案显然就是。
DP方程的转移显然：
哦，对了数组存的是第天到第天都走同一条最短路的花费。
对于数组的初始化，很简单，对于每一个，先把到天之间封闭的码头全部设为不可走，跑一遍最短路即可，初值为无穷。

代码

#include<bits/stdc++.h>
#define ll long long
const ll N=1e2+5,INF=0x3f3f3f3f,mod=998244353;
using namespace std;

ll n,m,k,ee,cnt,d;
ll head[N],dis[N],vis[N],cant_vis[N],cl[N][N];
ll cost[N][N],dp[N];
struct node
{
    ll to,nxt,dis;
}e[N<<1];

inline ll read()
{
    register ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

void add(ll u,ll v,ll w)
{
    e[++cnt].dis=w;
    e[cnt].nxt=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}

void spfa()
{
    for(ll i=1;i<=m;i++) dis[i]=1e8,vis[i]=0;
    queue<ll> q;
    dis[1]=0;
    q.push(1);
    while(!q.empty())
    {
        ll x=q.front();
        q.pop();
        vis[x]=0;
        for(ll i=head[x];i;i=e[i].nxt)
        {
            ll v=e[i].to;
            if(cant_vis[v]) continue;
            if(dis[v]>dis[x]+e[i].dis)
            {
                dis[v]=dis[x]+e[i].dis;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
 } 

int main()
{
    n=read();m=read();k=read();ee=read();
    for(ll i=1;i<=ee;i++)
    {
        ll u,v,w;
        u=read();v=read();w=read();
        add(u,v,w);add(v,u,w);
    }
    d=read();
    for(ll i=1;i<=d;i++)
    {
        ll t=read(),x=read(),y=read();
        for(ll j=x;j<=y;j++) cl[t][j]=1;
    }
    for(ll i=1;i<=n;i++)
     for(ll j=1;j<=n;j++)
     {
        memset(cant_vis,0,sizeof(cant_vis));
        for(ll r=i;r<=j;r++)
          for(ll l=1;l<=m;l++)
          if(cl[l][r]) cant_vis[l]=1;
        spfa();
        cost[i][j]=dis[m];
     }
    memset(dp,0x7f,sizeof(dp));
    for(ll i=1;i<=n;i++)
    {
        dp[i]=(ll)cost[1][i]*i;
        for(ll j=i-1;j>=0;j--)
            dp[i]=min(dp[i],dp[j]+cost[j+1][i]*(i-j)+k);
    }
    printf("%lld",dp[n]);
    return 0;
}

小结

哦，对了，虽然数据小还是要记得开
总所周知，不开见祖宗