P1772 [ZJOI2006] 物流运输

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e8;
class solve{
	public:
		int n,m,k,E;
		priority_queue < pair < int , int > > q;
		struct node{
			int nt,to,w;
		}e[1111];
		long long f[1111];
		int h[1111];
		int cnt,times[1111][1111];
		int vis[1111];
		int dis[1111];
        int v[1111];
		long long cost[1111][1111];
		inline void add(int x,int y,int w){e[++cnt]=(node){h[x],y,w};h[x]=cnt;}
		//求最短路 
		int dijkstra(){
			memset(dis,0x3f3f3f3f,sizeof(dis));
            memset(v,0,sizeof(v));
			dis[1]=0;
			q.push(make_pair(0,1));
			while(!q.empty()){
				int u=q.top().second;
				q.pop();
				if(v[u])continue;
                v[u]=1;
				for(int i=h[u]; i; i=e[i].nt){
					int v=e[i].to;
					if(vis[v])continue;
					if(dis[v]>dis[u]+e[i].w)
					{
						dis[v]=dis[u]+e[i].w;
						q.push(make_pair(-dis[v],v));
					}
				}
			}
			return dis[m];
		}
		void main()
		{
			memset(times,0,sizeof(times));
			cnt=0;
			scanf("%d%d%d%d",&n,&m,&k,&E);
			for(int i=1,x,y,w; i<=E; i++){
				scanf("%d%d%d",&x,&y,&w);
				add(x,y,w);add(y,x,w);
			}
			int d;
			scanf("%d",&d);
			//记录每一个码头在j天的状态 
			for(int i=1,x,y; i<=d; i++){
				int p;
				scanf("%d%d%d",&p,&x,&y);
				for(int j=x; j<=y; j++)
					times[p][j]=1;
			}
			//计算第i天到底j天是只用同一条路径的路径长度 
			for(int i=1; i<=n; i++){
				for(int j=1; j<=n; j++){
					memset(vis,0,sizeof(vis));
					for(int Y=i; Y<=j; Y++)
					for(int X=1; X<=m; X++)
							if(times[X][Y]==1)vis[X]=2;
							//第i天到第j天都不可以用的码头要记录下来 
					cost[i][j]=dijkstra();
				}
			}
			memset(f,0x7ffff,sizeof(f));
			for(int i=1; i<=n; i++){
				f[i]=(long long)cost[1][i]*i;
				for(int j=i-1; j>=0; j--){
					f[i]=min(f[i],f[j]+(long long)cost[j+1][i]*(i-j)+k);
					//dp方程，前i天的最小值为前j天的最小值加上j+1至i天用同一个路径的值加上变换的额外成本 
				}
			}
			cout<<f[n]<<endl;
		}
}x;
int main()
{
	x.main();
}