Loading...

bzoj 1003 物流运输

check评论:0 条 remove_red_eye浏览量:65 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-11-18

链接

给你一张无向图,让你求$n$天$1-m$最短路长度总和最小值,有部分时间一些点不能走,每次更换最短路要加代价$K$

因为范围很小,可以$n^2$枚举求出$i-j$这几天间都可以走的最短路,记为$dp[i][j]$,然后$dp$即可,$t[i]$代表前$i$天最小代价,$t[i]=min(t[j]+dp[j+1][i]+k,dp[1][i]),j\in [1,i-1]$

/*  Never Island  */
/*deco loves Chino*/
/* Summer Pockets */
#include <bits/stdc++.h>
using namespace std;
int dp[1100][1100],head[250],dis[250],n,m,k,ee,dk,tmm[250][1100];
int t[1100],cnt,acc[250],vis[250];
struct edge
{
    int next,to,dis;
}e[2200];
void add(int u,int v,int d)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].dis=d;
    head[u]=cnt;
}
void spfa()
{
    queue<int> q;
    memset(vis,0,sizeof(vis));
    q.push(1);
    dis[1]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].dis&&acc[v]==0)
            {
                dis[v]=dis[u]+e[i].dis;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m>>k>>ee;
    for(int i=1;i<=ee;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    cin>>dk;
    for(int i=1;i<=dk;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        for(int j=y;j<=z;j++)
        {
            tmm[x][j]=1;
        }
    }
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        memset(acc,0,sizeof(acc));
        for(int j=i;j<=n;j++)
        {
            for(int k=1;k<=m;k++)
            {
                if(tmm[k][j])
                {
                    acc[k]=1;
                }
            }
            memset(dis,0x3f,sizeof(dis));
            spfa();
            if(dis[m]==0x3f3f3f3f)
            {
                break;
            }
            dp[i][j]=dis[m]*(j-i+1);
        }
    }
    memset(t,0x3f,sizeof(t));
    for(int i=1;i<=n;i++)
    {
        t[i]=dp[1][i];
        for(int j=1;j<i;j++)
        {
            t[i]=min(t[i],t[j]+dp[j+1][i]+k);
            
        }
    }
    cout<<t[n];
}

deco 没有放弃

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名