BZOJ1003: [ZJOI2006] 물류운송trans DP+SPFA

dp[i]=min(dp[j]+dur[j+1][i]*(i-j)+K)dur(i,j)는 i일에서 j일까지 길을 바꾸지 않는 최단 거리를 나타낸다

1003: [ZJOI2006] 물류 운송trans

Time Limit: 10 Sec  
Memory Limit: 162 MB
Submit: 4001  
Solved: 1671
[ Submit][ Status][ Discuss]

Description

물류회사는 한 무더기의 화물을 부두 A에서 부두 B로 운송해야 한다.화물량이 비교적 많기 때문에, n일이 걸려야만 운송을 끝낼 수 있다.화물 운송 과정 중에는 일반적으로 여러 부두를 옮겨 세워야 한다.물류 회사는 통상적으로 전체 운송 과정에 대해 엄격한 관리와 추적을 실시하기 위해 고정된 운송 노선을 설계할 것이다.여러 가지 요소의 존재로 인해 어떤 부두에서는 화물을 하역할 수 없을 때가 있다.이때 반드시 운송 노선을 수정하여 화물이 제때에 목적지에 도착할 수 있도록 해야 한다.그러나 노선을 수정하는 것은 매우 번거로운 일로 추가 비용을 초래할 수 있다.따라서 물류회사는 n일의 운송 계획을 제정하여 총 원가를 가능한 한 줄일 수 있기를 희망한다.

Input

첫 번째 줄은 네 개의 정수 n(1<=n<=100), m(1<=m<=20), K와 e이다.n은 화물 운송에 소요되는 일수, m은 부두 총수, K는 매번 운송 노선을 수정하는 데 소요되는 원가를 나타낸다.다음 e행은 줄마다 하나의 항로 묘사로 세 개의 정수를 포함하고 순서대로 항로가 연결된 두 개의 부두 번호와 항로 길이(>0)를 나타낸다.그중 부두 A 번호는 1이고 부두 B 번호는 m이다.단위 길이의 운송 비용은 1이다.항로가 양방향이다.다음 행은 정수 d이고 그 다음 d행은 각 행마다 세 개의 정수 P(1 < P < m), a, b(1 < = a < = b < = n)입니다.번호가 P인 부두는 a일째부터 b일째까지 화물을 하역할 수 없음(머리와 꼬리 포함)을 나타낸다.같은 부두는 여러 시간 내에 사용할 수 없을 수도 있다.그러나 어느 때든지 부두 A에서 부두 B까지의 운송 노선이 최소한 하나 존재한다.

Output

최소한의 총 원가를 나타내는 정수를 포함했다.총 원가 = n일 운송 노선의 길이의 합계 + K* 운송 노선의 변경 횟수.

Sample Input

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

Sample Output

32

HINT

3일 전에는 1-4-5, 이틀 후에는 1-3-5로 총 원가(2+2)*3+(3+2)*2+10=32

Source

/* ***********************************************
Author        :CKboss
Created Time  :2015 04 30      10 58 56 
File Name     :BZOJ1003.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

typedef long long int LL;

const int maxn=1000;
const LL INF=0x3f3f3f3f3f3f3f3f;

int n,m,K,e,d;

struct Edge
{
	int to,next,len;
}edge[maxn];

int Adj[50],Size;

void init()
{
	memset(Adj,-1,sizeof(Adj)); Size=0;
}

void add_edge(int u,int v,int len)
{
	edge[Size].to=v; edge[Size].next=Adj[u];
	edge[Size].len=len; Adj[u]=Size++;
}

void Add_Edge(int u,int v,int len) { add_edge(u,v,len); add_edge(v,u,len); }

bool go[50][200];
LL dur[200][200];
bool cango[50];

/*************spfa********************/

int dist[50],cq[50];
bool inq[50];

bool spfa()
{
	memset(dist,63,sizeof(dist));
	memset(cq,0,sizeof(cq));
	memset(inq,false,sizeof(inq));
	dist[1]=0; queue<int> q;
	q.push(1); inq[1]=true; cq[1]=1;
	
	while(!q.empty())
	{
		int u=q.front(); q.pop();
		for(int i=Adj[u];~i;i=edge[i].next)
		{
			int v=edge[i].to;
			int len=edge[i].len;
			if(cango[v]==false) continue;
			if(dist[v]>dist[u]+len)
			{
				dist[v]=dist[u]+len;
				if(!inq[v])
				{
					inq[v]=true;
					cq[v]++;
					if(cq[v]>=m) return false;
					q.push(v);
				}
			}
		}
		inq[u]=false;
	}
	return true;
}

LL dp[200];

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

	init();
	memset(go,true,sizeof(go));
	scanf("%d%d%d%d",&n,&m,&K,&e);
	for(int i=0;i<e;i++)
	{
		int u,v,l;
		scanf("%d%d%d",&u,&v,&l);
		Add_Edge(u,v,l);
	}
	scanf("%d",&d);
	for(int i=0;i<d;i++)
	{
		int p,a,b;
		scanf("%d%d%d",&p,&a,&b);
		for(int j=a;j<=b;j++) go[p][j]=false;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			memset(cango,true,sizeof(cango));
			for(int k=1;k<=m;k++)
			{
				bool fg=true;
				for(int l=i;l<=j&&fg;l++) 
					if(go[k][l]==false) fg=false;
				if(fg==false) cango[k]=false;
			}
			spfa();
			dur[i][j]=1LL*dist[m];
		}
	}
	memset(dp,63,sizeof(dp));
	dp[0]=0;dp[1]=dur[1][1];
	for(int i=2;i<=n;i++)
	{
		if(dur[1][i]!=INF) dp[i]=dur[1][i]*i;
		for(int j=1;j+1<=i;j++)
		{
			if(dur[j+1][i]==INF) continue;
			dp[i]=min(dp[i],dp[j]+dur[j+1][i]*(i-j)+K);
		}
	}
	printf("%lld
",dp[n]);
    return 0;
}