ZJOI2006

题目大意

就是说，你需要跑次最短路，然后对于某些时间，有些点是无法到达的
然后如果你跑路的路径发生了改变的话，那么对于每次改变都会有 的花费

分析

那么显然贪心是错误的，考虑动态规划
设 表示跑到第 天的最小花费，那么最后的答案显然是
那么现在考虑转移：
就是说从第 天开始一直到第 天都是同一条路线，然后花费了 的代价改变了一下这个路线，这个 应该是很显然的

Code

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int maxn = 1e2 + 10;
const int maxm = 1e4 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int Size = (sizeof (int)) * maxn;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

int n, m, k, e, cur;
int head[maxn], edge[maxm], lst[maxm], cost[maxm];
int dis[maxn], dp[maxn];
bool vis[maxn], in_q[maxn], flag[maxn][maxn];

deque <int> Q;

inline int SPFA()
{
    memset (dis, 0x3f, Size);
    Q.push_back(1);
    dis[1] = 0;
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop_front();
        in_q[u] = 0;
        for (int i = head[u]; i; i = lst[i]) {
            int v = edge[i];
            if (dis[v] <= dis[u] + cost[i] || vis[v]) continue;
            dis[v] = dis[u] + cost[i];
            if (in_q[v]) continue;
            if (Q.empty() || dis[v] <= dis[Q.front()]) Q.push_front(v);
            else Q.push_back(v);
            in_q[v] = 1;
        }
    }
    return dis[m];
}

inline void addedge(int u, int v, int w)
{
    lst[++cur] = head[u];
    head[u] = cur;
    edge[cur] = v;
    cost[cur] = w;
}

inline int min(int x, int y)
{
    if (x < y) return x;
    return y;
}

int main()
{
    n = __read(), m = __read(), k = __read(), e = __read();
    while (e--) {
        int a = __read(), b = __read(), c = __read();
        addedge(a, b, c), addedge(b, a, c);
    }

    e = __read();
    while (e--) {
        int a = __read(), b = __read(), c = __read();
        for (int i = b; i <= c; ++i) flag[i][a] = 1;
    }

    memset (dp, 0x3f, Size);
    dp[0] = -k;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) vis[j] = 0;
        for (int j = i; j >= 1; --j) {
            for (int k = 1; k <= m; ++k)
                if (flag[j][k]) vis[k] = 1;
            int temp = SPFA();
            if (temp == inf) break;
            dp[i] = min(dp[i], dp[j - 1] + (i - j + 1) * temp + k);
        }
    }

    printf ("%d\n", dp[n]);
}