P1772 [ZJOI2006] 物流运输

P1772 [ZJOI2006] 物流运输

题意:

需要将物品从 \(A\) 移动到 \(B\) ，需要 \(n\) 天才能运输完成，运输过程中需要转停很多个码头。

求指定一个 \(n\) 天的运输计划，使得总成本尽可能的少。

给出 \(n\) 货物运输需要的天数， \(m\) 码头总数， \(k\) 每次修改运输路线需要的成本 ，\(e\) 航线条数。

然后给出双向航线的起始点和终点。

然后是整数 \(d\) ，下面 \(d\) 行每行表示三个整数 \(p,a,b\) 表示编号为 \(p\) 的码头在 \([a,b]\) 天内无法装卸货物，同一个码头可能多个时间段不可用，任何时间至少一条从 \(A\) 到 \(B\) 的路线。

数据范围:

\(1 \le n \le 100\)，\(1\le m \le 20\) \(,1 \le k \le 500\), \(1 \le e \le 200\)

思路1:

假设每天所有码头都可以走的话，最终结果肯定就是最短路径的 \(*n\)，但是现在因为一些码头在固定的天数无法走，如果单独选择每一天的最短路径加起来的话一定就是最短的，但是因为换路还要额外付出 \(k\) 的代价，所以就需要用 \(dp\) 来求怎么组合起来可以使得n天的总代价最小。

设状态 \(dp[i]\) 为到第 \(i\) 天的最短代价，那么它可能是由一段一段相同路组成的，所以就可以枚举换路点。那么处理出co[i][j]为从第 \(i\) 天到第 \(j\) 天走同一条路的最小代价。

状态转移方程:

dp[i] = min(dp[i], dp[j - 1] + co[j][i] + ((j == 1) ? 0 : k));

思路2:

出所有的路径然后dp ，这里找路径是深搜边，最终得到的边数可能会非常大，记录路径其实像记录的是经过部分点的路径，比如经过1，3，4的路径，这样的路径可能会有很多条，但是实际上想要存储的只是经过1,3,4的最短路径。

此题点非常少,而边可能很多,所以可能造成的重复状态很多

一共有20个点，头和尾是一定要经过的，所以可以得出不同的路径条数其实只有2^18 = 262144条，之后利用求出这些状态的最短路然后dp

dp 最直观的状态转移方程是dp[i][j] = min( dp[I - 1,x] + (x != j)*k + cost[j])

但是这样的时间复杂度是\(2^{28} * 2 ^ {18}\)，但是注意到 \(dp[I - 1,x]\) 只有当 \(x == j\) 的时候，等式才存在不一样，所以可以直接在前一个循环里面存下dp[I - 1][x]的最小值，就可以快速得到答案了。

$ dp[i][j] = min(last + k,f[I - 1,j]) + cost[j]$

//思路1:
using namespace std;
const long long N = 105, M = 25, inf = 1e9;
long long n, m, k, e;

long long dis[M][M];
// ok[i][j]:第i个码头在第j天是否可停留
long long ok[M][N];

long long tem[M][M];
long long co[N][N];
long long dp[N];

void floyd()
{
    for (long long k = 1; k <= m; k++)
        for (long long i = 1; i <= m; i++)
            for (long long j = 1; j <= m; j++)
                tem[i][j] = min(tem[i][j], tem[i][k] + tem[k][j]);
}

long long get(long long ok[M][N], long long id, long long l, long long r)
{
    return ok[id][r] - ok[id][l - 1];
}

int main()
{
    scanf("%lld%lld%lld%lld", &n, &m, &k, &e);

    for (long long i = 1; i <= m; i++)
        for (long long j = 1; j <= m; j++)
            if (i != j)
                dis[i][j] = 1e9;

    for (long long i = 1; i <= e; i++)
    {
        long long a, b, c;
        scanf("%lld%lld%lld", &a, &b, &c);
        dis[a][b] = dis[b][a] = c;
    }

    long long d;
    scanf("%lld", &d);
    for (long long j = 1; j <= d; j++)
    {
        long long p, a, b;
        scanf("%lld%lld%lld", &p, &a, &b);
        for (long long i = a; i <= b; i++)
            ok[p][i] = 1;
    }

    //前缀和处理，使得后面可以快速得知 i 码头在[一个区间中]是否存在不可走的情况
    for (long long i = 1; i <= m; i++)
        for (long long j = 1; j <= n; j++)
            ok[i][j] += ok[i][j - 1];

    for (long long i = 1; i <= n; i++)
        for (long long j = 1; j <= n; j++)
            co[i][j] = inf;

    for (long long i = 1; i <= n; i++)
        for (long long j = i; j <= n; j++)
        {
            memcpy(tem, dis, sizeof dis);
            for (long long h = 1; h <= m; h++)
                //如果此时不可走，直接定义为正无穷
                if (get(ok, h, i, j) != 0)
                    for (long long t = 1; t <= m; t++)
                        tem[h][t] = inf;
            floyd();
            if (tem[1][m] < inf)
                co[i][j] = co[j][i] = tem[1][m] * (j - i + 1);
            else
                co[i][j] = co[j][i] = inf;
        }

    for (long long i = 1; i <= n; i++)
        dp[i] = inf;
    for (long long i = 1; i <= n; i++)
    {
        for (long long j = 1; j <= i; j++)
            dp[i] = min(dp[i], dp[j - 1] + co[j][i] + ((j == 1) ? 0 : k));
    }
    printf("%lld\n", dp[n]);
    return 0;
}