NKOJ 3761 送外卖（最短路+状压dp）

发表于 |
字数统计: 1,374字 | 阅读时长 ≈ 6min

P3761送外卖

问题描述

暑期期间，何老板闲来无事，于是买了辆摩托车，签约某团外卖，跑起来送外卖的业务。
何老板负责的区域里有n个住宅小区(编号1到n)，小区间通过m条双向道路相连，两个小区间最多只有一条道路相连，也不存在某小区自己到它自己的道路。每条道路有一定的长度。
何老板先到1号小区的餐馆去领餐，然后去k个小区送餐(编号2,3,4,...,k+1)，最终到n号小区的加油站去给摩托车加油。要到k个小区去送餐，根据下单时间，公司规定了其中某些小区送餐的先后顺序，比如i小区的餐必须在给j小区送餐前送到。何老板希望在满足公司要求的情况下，使得行走的总路程最少，请你帮他计算一下。
例如，下图所示，起点为1号终点为8号小区。期间要给2、3、4、5号小区送餐。公司规定，给2号小区送餐后才能给3号小区送餐，给3号小区送餐后才能给4、5号小区送餐。最短的行程方案是1—>2—>4—>3—>4—>5—>8,总路程为19。

这里写图片描述

注意，可以先经过某些后送餐的小区而不停下来给它们送餐。假如，要送4号小区后才能给3号小区送餐，何老板可以从2号经过3号到达4号小区，中间虽然经过了3号小区，但他没有停下来，这样就不违法公司的规定了。

输入格式

第一行，3个空格间隔的整数n,m,k

接下来m行，每行三个整数x,y,z表示小区x也小区y间有一条长度为z的道路(1<=x,y<=n   1<=z<=1000)

接下来一行，一个整数t,表示公司有t条要求(0<=t<=k*(k-1)/2)

接下来t行，每行两个整数x和y,表示给x小区送餐后才能给y号小区送餐
(2<=x,y<=k+1   x!=y)

输出格式

一行，一个整数，表示所求最短总路程。

样例输入

8 15 4
1 2 3
1 3 4
1 4 4
1 6 2
1 7 3
2 3 6
2 4 2
2 5 2
3 4 3
3 6 3
3 8 6
4 5 2
4 8 6
5 7 4
5 8 6
3
2 3
3 4
3 5

样例输出

19

观察题目我们发现需要送餐的小区最多只有20个，于是想到状压dp来处理。再观察发现我们可以预先求出这20个小区+1号点+n号点两两之间的最短路，那么我们就将原图缩小成了只有22个点的新图，两两之间的距离就是原图中的最短路。之后写出dp方程
$$F[i][S]=min{F[k][j]+dis[k][i]},S=j|(1<<k-2)$$
这个方程表示从k号点走到i号点，j为经过的点集。
当然我们还要注意到走到一个点时，必须满足一些关系，即有些点需要先到。那么我们可以用拓扑排序的方法预处理出这些关系。即对于点x，用$P$表示在x之前送餐的点的集合。具体实现可参照代码。
那么我们在转移时只需要满足$S\&P[i]==P[i]$即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#define N 23333
#define M 433333
using namespace std;
queue<int>S,Q;
int T,n,m,k,t,tt[55][55],RU[55],P[55];
int TOT,LA[N],NE[M],EN[M],LE[M];
int dis[N][25],F[25][1050000],dist[25][25],ans=1e9;
bool mark[N];
void ADD(int x,int y,int z)
{
	TOT++;
	EN[TOT]=y;
	LE[TOT]=z;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void SPFA(int s)
{
	int i,x,y;
	for(i=1;i<=n;i++)dis[i][s]=1e9;
	dis[s][s]=0;mark[s]=1;Q.push(s);
	while(!Q.empty())
	{
		x=Q.front();
		Q.pop();
		mark[x]=0;
		for(i=LA[x];i;i=NE[i])
		{
			y=EN[i];
			if(dis[y][s]>dis[x][s]+LE[i])
			{
				dis[y][s]=dis[x][s]+LE[i];
				if(!mark[y])mark[y]=1,Q.push(y);
			}
		}
	}
}
int main()
{
	int i,j,p,x,y,z;
	scanf("%d%d%d",&n,&m,&k);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		ADD(x,y,z);ADD(y,x,z);
	}
	scanf("%d",&t);
	for(i=1;i<=t;i++)
	{
		scanf("%d%d",&x,&y);
		tt[x][y]=1;RU[y]++;
	}
	for(i=2;i<=k+1;i++)if(!RU[i])S.push(i);
	while(!S.empty())
	{
		x=S.front();S.pop();
		for(i=2;i<=k+1;i++)
		if(tt[x][i])
		{
			RU[i]--;
			tt[x][i]=0;
			P[i]=P[i]|(1<<x-2);
			if(!RU[i])S.push(i);
		}
	}
	for(i=1;i<=k+1;i++)SPFA(i);
	T=k+2;
	for(i=1;i<T;i++)
	{
		for(j=1;j<T;j++)dist[i][j]=dis[j][i];
		dist[i][T]=dis[n][i];
		dist[T][i]=dis[n][i];
	}
	P[T]=(1<<k)-1;
	memset(F,-1,sizeof(F));
	F[1][0]=0;
	for(i=0;i<P[T];i++)
	for(j=1;j<T;j++)
	{
		if(F[j][i]==-1)continue;
		for(p=2;p<T;p++)
		{
			x=i|(1<<(p-2));
			if(((x&P[p])==P[p])&&(F[p][x]==-1||F[p][x]>F[j][i]+dist[j][p]))
			F[p][x]=F[j][i]+dist[j][p];
		}
	}
	for(i=1;i<T;i++)
	if(F[i][P[T]]!=-1)ans=min(ans,F[i][P[T]]+dist[i][T]);
	cout<<ans;
}