luogu P1772 [ZJOI2006] 物流运输 （dp， 最短路）

https://www.luogu.com.cn/problem/P1772

虽然是图论背景，但是1-n天之间是线性关系。没法贪心决策，考虑dp：
我本来写的dp是i-1转移到i，但是这样没法处理哪一天能走哪些最短路
需要改一下dp的转移：
连续几天走相同的路径相当于直接跳过这几天，那就是经典的线性不连续转移
f[i] = min(f[i], f[j] + cost[j + 1][i] * (i - j) + K);
这样i - j的最短路可以算出

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false) ,cin.tie(0), cout.tie(0);
//#pragma GCC optimize(3,"Ofast","inline")
#define ll long long
#define PII pair<int, int>
//#define int long long
const int N = 1e5 + 5;
const int M = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double PI = acos(-1.0);
struct Edge {
    int u, v, w;
} eds[205];
struct Day {
    int p, a, b;
}day[205];

int h[205], e[205 << 1], ne[205 << 1], w[205 << 1], idx;
bool st[205];

int dist[25]; int m;
ll cost[105][105], f[105]; 
void add( int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}
int spfa() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1); st[1] = 1;
     while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return dist[m];
}
int main() {
    IOS
    int n, K, e, d; cin >> n >> m >> K >> e;
    for ( int i = 1; i <= e; ++ i ) {
        cin >> eds[i].u >> eds[i].v >> eds[i].w;
    }
    cin >> d;
    for( int i = 1; i <= d; ++ i) {
        int p, a, b; cin >> p >> a >> b;
        day[i] = {p, a, b};
    }
    for ( int i = 1; i <= n; ++ i ) {
        for ( int j = i; j <= n; ++ j ) {
            memset(h, -1, sizeof h); memset(st, 0, sizeof st); idx = 0;

            for (int k = 1; k <= d; ++ k) {
                int p = day[k].p, a = day[k].a, b = day[k].b;
                if( b < i || a > j ) {}
                else {st[p] = 1; }
            }

            for ( int k = 1; k <= e; ++ k ) {
                if(!st[eds[k].u] && !st[eds[k].v]) {
                    add(eds[k].u, eds[k].v, eds[k].w);
                    add(eds[k].v, eds[k].u, eds[k].w);
                }
            }
            cost[i][j] = spfa();
        }
    }

    for ( int i = 1; i <= 100; ++ i ) f[i] = 1e18;
    f[0] = -K;
    for ( int i = 1; i <= n; ++ i ) {
        for ( int j = 0; j < i; ++ j ) {
            f[i] = min(f[i], f[j] + cost[j + 1][i] * (i - j) + K);
           // cout << j << " " << i << " " << f[i] << '\n';
        }
    }
    cout << f[n] << '\n';
    return 0;
}