做题记录整理dp15 P1772. [ZJOI2006] 物流运输（2022/9/28）

P1772. [ZJOI2006] 物流运输

图论+dp
首先看数据范围这么小，其实就可以猜到很可能是先把i到j天的最短路都求出来
然后就会发现dp方程很简单了

dp[i]=min(dp[j]+最短路[j+1][i]*(i-j)+k)

dp,i就是前i天的最小代价
选择在第j天改道
然后还有个坑点就是要开long long（。。。这个是看题解才知道的）

#include<bits/stdc++.h>
#define for1(i,a,b) for(ll i = a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;
ll d,cnt,hd[105],dis[105],vis[105],vis2[105];
ll jl[505][505],dp[505],cl[25][505];
ll n,m,k,e,t;
priority_queue<pair <int,int> , vector<pair <int,int> >, greater<pair <int,int> > > q;
const ll inf=1e8+5;
struct node{
	int to;
	int nex;
	int w;
}a[10005];
void ru(int x,int y,int z){
	a[++cnt].to=y;
	a[cnt].w=z;
	a[cnt].nex=hd[x];
	hd[x]=cnt;
}
void dij(){
	for1(i,1,m) dis[i]=inf,vis[i]=0;
	while(!q.empty()) q.pop();
	dis[1]=0;
	q.push(mp(0, 1));
	while(!q.empty())
	{
		int x = q.top().second;
		q.pop();
		if (vis[x] == 1)
			continue;
		vis[x] = 1;
		for(int i=hd[x];i;i=a[i].nex)
		{
			int v=a[i].to;
			if(vis2[v]) continue;
			if(dis[v]>dis[x]+a[i].w)
			{
				dis[v]=dis[x]+a[i].w;
				q.push(mp(dis[v], v));
			}
		}
	}
}
int main()
{
	cin>>n>>m>>k>>e;
	ll x,y,z;
	for1(i,1,e)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		ru(x,y,z);
		ru(y,x,z);
	}
	cin>>d;
	for1(i,1,d)
	{
		scanf("%lld%lld%lld",&t,&x,&y);
		for1(j,x,y) cl[t][j]=1;
	}
	memset(dp,0x3f,sizeof(dp));
	for1(i,1,n)
		for1(j,1,n)
		{
			memset(vis2,0,sizeof(vis2));
			for1(r,i,j)
				for1(l,1,m)
					if(cl[l][r]) vis2[l]=1;
			dij();
			jl[i][j]=dis[m];
		}

	for1(i,1,n)
	{
		dp[i]=jl[1][i]*i;
		for(int j=i-1;j>=0;j--)
			dp[i]=min(dp[i],dp[j]+jl[j+1][i]*(i-j)+k);
	}
	printf("%lld",dp[n]);
    return 0;
}