洛谷 - P1772 [ZJOI2006]物流运输

传送门：洛谷 - P1772

思路分析

先预处理出f[i][j]表示第i天到j天的最短路
然后就可以转移了

样例输入

 5 5 10 8
 1 2 1
 1 3 3
 1 4 2
 2 3 2
 2 4 4
 3 4 1
 3 5 2
 4 5 2
 4
 2 2 3
 3 1 1
 3 3 3
 4 4 5

样例输出

32

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) x.size()
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N = 500;

struct node {
    int to,val,next;
} e[N];

int n,m,k,s;
int head[N],dis[N],vis[N],dp[N],cnt,c[N][N],cvis[N],f[N][N];

void add(int u,int v,int w) {
    e[++cnt].to=v;
    e[cnt].val=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}

void spfa(int s) {
    for(int i=0; i<=m; i++) dis[i]=1e9;
    mem(vis,0);
    dis[s]=0;
    vis[s]=1;
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        vis[u]=0;
        q.pop();
        for(int i=head[u]; i; i=e[i].next) {
            int v=e[i].to;
            if(dis[v]>(dis[u]+e[i].val) && !cvis[v]) {
                dis[v]=dis[u]+e[i].val;
                if(!vis[v]) {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }

}

signed main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    cin>>n>>m>>k>>s;
    for(int i=1; i<=s; i++) {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    int q;
    cin>>q;
    while(q--) {
        int x,l,r;
        cin>>x>>l>>r;
        for(int i=l; i<=r; i++) c[x][i]=1;
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            mem(cvis,0);
            for(int r=i; r<=j; r++) {
                for(int x=1; x<=m; x++) {
                    if(c[x][r]) cvis[x]=1;
                }
            }
            spfa(1);
            f[i][j]=dis[m];
        }
    }
    mem(dp,INF);
    for(int i=1; i<=n; i++) {
        dp[i]=f[1][i]*i;
        for(int j=1; j<=i; j++) {
            dp[i]=min(dp[i],dp[j-1]+(i-j+1)*f[j][i]+k);
        }
    }
    cout<<dp[n]<<endl;





    return 0;
}