ZJOI2006 物流运输

wjh15101051's space

卧薪尝胆，厚积薄发。

ZJOI2006 物流运输

Date: Fri May 25 11:57:29 CST 2018

In Category: NoCategory

Description:

一个图中，一些点在一段时间内不能通过，最小化在全部 $d$ 天内从 $1$ 到 $N$ 的长度之和 $+$ 改换路线的次数 $\times$ 系数 $k$ 。

$1 \le d \le 100$ $ 1 \le N \le 20$

Solution:

设 $g[i][j]$ 表示在 $i$ 到 $j$ 时间段内只走一条路线的最短距离，取出在 $i$ 到 $j$ 时间段内可以经过的点跑 $SPFA$ 即可求出。

然后 $DP$ ， $f[i]$ 表示 $1\dots i$ 时间段内最小花费， $f[i] = max(f[j]+g[j+1][i]+k)(0 \le j <i)$ ，多加了一个 $k$ ，再减掉就好。

Code:


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

typedef long long ll;

#define INF 0x3f3f3f3f3f3f3f3f

int d,n,m;

ll k;

#define MAXD 110

#define MAXN 22

#define MAXP 1000000

struct edge

{

	int to,nxt;

	ll v;

}e[(MAXN * MAXN) << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,ll c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

int p;

int h[MAXP],l[MAXP],r[MAXP];

bool v[MAXN];

bool inq[MAXN];

ll dis[MAXN];

ll g[MAXD][MAXD];

ll f[MAXD];

void spfa()

{

	memset(dis,0x3f,sizeof(dis));

	memset(inq,false,sizeof(inq));

	dis[1] = 0;

	inq[1] = true;

	queue<int> q;

	q.push(1);

	while(!q.empty())

	{

		int k = q.front();q.pop();

		inq[k] = false;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(!v[e[i].to])continue;

			if(dis[e[i].to] > dis[k] + e[i].v)

			{

				dis[e[i].to] = dis[k] + e[i].v;

				if(!inq[e[i].to])

				{

					inq[e[i].to] = true;

					q.push(e[i].to);

				}

			}

		}

	}

	return;

}

int main()

{

	scanf("%d%d%lld%d",&d,&n,&k,&m);

	int a,b;ll c;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%lld",&a,&b,&c);

		add(a,b,c);add(b,a,c);

	}

	scanf("%d",&p);

	for(int i = 1;i <= p;++i)

	{

		scanf("%d%d%d",&h[i],&l[i],&r[i]);

	}

	for(int i = 1;i <= d;++i)

	{

		for(int j = i;j <= d;++j)

		{

			for(int k = 1;k <= n;++k)v[k] = true;

			for(int k = 1;k <= p;++k)

			{

				if(i <= r[k] && j >= l[k])

				{

					v[h[k]] = false;

				}

			}

			spfa();

			g[i][j] = dis[n];

		}

	}

	memset(f,0x3f,sizeof(f));

	f[0] = 0;

	for(int i = 1;i <= d;++i)

	{

		for(int j = 0;j < i;++j)

		{

			if(g[j + 1][i] < INF)f[i] = min(f[i],f[j] + g[j + 1][i] * (long long)(i - j) + k);

		}

	}

	cout << f[d] - k << endl;

	return 0;

}

In tag: 图论-SPFA DP-DP

wjh15101051