[Solution][SSSP][Dynamic Programming]ZJOI2006 物流运输

【题目】

戳这里

【思路】

SPFA+DP.

暴力枚举出时间段内的最短路长度。

然后进行简单的DP。

设第1~i时刻的最小费用为DP[i],则有:

最终答案为.

时间复杂度

这样其实默认为每两个用来更新当前决策的路径走法都是不同的,但是会不会有可能相同呢???没理解。。。

由于开始认为是从时刻0开始转移也需要转移费用,实际不需要这个费用,所以减去一个转移费用。

【代码】

/**************************************************************
    Problem: 1003
    User: wyfcyx
    Language: C++
    Result: Accepted
    Time:60 ms
    Memory:1008 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int INF = 0x1f1f1f1f;
inline int _min(int a , int b)
{
    return a < b ? a : b;
}
int n , head[101] , dis[101] , end[10001] , next[10001] , len[10001];
bool allow[101];
void addedge(int a , int b  ,int _len)
{
    static int q = 1;
    end[q] = b;
    len[q] = _len;
    next[q] = head[a];
    head[a] = q;
    q++;
}
queue<int> q;
bool inq[101];
int spfa()
{
    memset(inq , 0 , sizeof(inq));
    inq[1] = 1;
    q.push(1);
    memset(dis , 0x1f , sizeof(dis));
    dis[1] = 0;
    int i , j;
    while(!q.empty())
    {
        i = q.front();
        q.pop();
        inq[i] = 0;
        for(j = head[i] ; j ; j = next[j])
        {
            if (allow[end[j]] && dis[end[j]] > dis[i] + len[j])
            {
                dis[end[j]] = dis[i] + len[j];
                if (!inq[end[j]])
                {
                    inq[end[j]] = 1;
                    q.push(end[j]);
                }
            }
        }
    }
    return dis[n];
}
bool notallow[101][101];
int dp[101] , get[101][101];
int main()
{
    int L , m , cost;
    scanf("%d%d%d%d" , &L , &n , &cost , &m);
    int a , b , x;
    register int i , j , k , p;
    for(i = 1 ; i <= m ; ++i)
    {
        scanf("%d%d%d" , &a , &b , &x);
        addedge(a , b , x);
        addedge(b , a , x);
    }
    int num , ord , l , r;
    scanf("%d" , &num);
    while(num--)
    {
        scanf("%d%d%d" , &ord , &l , &r);
        for(i = l ; i <= r ; ++i)
            notallow[i][ord] = 1;
    }
    for(i = 1 ; i <= L ; ++i)
    for(j = i ; j <= L ; ++j)
    {
        memset(allow , 1 , sizeof(allow));
        for(k = i ; k <= j ; ++k)
        for(p = 2 ; p < n ; ++p)
            if (notallow[k][p])
                allow[p] = 0;
        get[i][j] = spfa();
    }
    memset(dp , 0x1f , sizeof(dp));
    dp[0] = 0;
    for(i = 1 ; i <= L ; ++i)
    for(j = 0 ; j < i ; ++j)
        if (get[j + 1][i] < INF)
            dp[i] = _min(dp[i] , dp[j] + get[j + 1][i] * (i - j) + cost);
    printf("%d" , dp[L] - cost);
    return 0;
}
comments powered by Disqus