自动搬运

查看原文

来自洛谷，原作者为

	若如初见 终于拿到了蓝钩 我也该和OI Say goodbye了

搬运于2025-08-24 21:45:27，当前版本为作者最后更新于2019-11-13 20:05:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

即将退役的选手来写篇题解

此题做法：拓扑排序 + DP

首先，根据题意我们可以得出，这是一张有向无环图（DAG），那我们也不难想到拓扑排序，同时做一遍 DP 。

由于数据范围比较小，可以设计出如下的 DP 模型-：

状态： $f[i][j]$ 表示经过 $j$ 时间能否到达 $i$ 号结点；

转移方程： $f[v][j]=f[u][j-edge[i].w]\ (j-edge[i].w\geq 0,(u,v)\in G)$

边界： $f[1][0]=1$

目标状态： $\min\{ j \},\ \text{s.t.}\ f[n][j]=1$

注意到有两个人要走，所以我们开两个 DP 数组进行转移。最后求出最小的 $j$ ，使得 $f1[n][j]=f2[n][j]=1$即可。

具体实现请看代码：

#include <cstdio>
#include <queue> 
#define rint register int //卡常加速
#define MAXN 105
using namespace std;
queue <int> q; //用队列进行拓扑排序
int n,m,cnt,head[MAXN],ind[MAXN]; 
//n:结点数 m：边数 head,cnt：链式前向星存图用 ind: 存储结点入度
bool f1[MAXN][MAXN*MAXN],f2[MAXN][MAXN*MAXN];  
  //DP数组
struct Edge{
	int next,to,w1,w2;
}edge[MAXN*MAXN];
  //链式前向星，w1、w2分别存储两个人走这条边所需的时间
inline void add(int u,int v,int w1,int w2){
	edge[++cnt].next=head[u];
	edge[cnt].to=v;
	edge[cnt].w1=w1;
	edge[cnt].w2=w2;
	head[u]=cnt;
} //加边
int main(){
	scanf("%d %d",&n,&m);
	for(rint i=1;i<=m;++i){
		int u,v,w1,w2;
		scanf("%d %d %d %d",&u,&v,&w1,&w2);
		add(u,v,w1,w2); //加边
		++ind[v]; //统计入度
	}
	for(rint i=1;i<=n;++i)
		if(!ind[i]) q.push(i); //入度为0的点入队
	f1[1][0]=f2[1][0]=1; //DP边界
	while(!q.empty()){ //拓扑排序板子
		int u=q.front();
		q.pop();
		for(rint i=head[u];i;i=edge[i].next){
			int v=edge[i].to;
			for(rint j=0;j<=10000;++j){
				if(j-edge[i].w1>=0) f1[v][j]|=f1[u][j-edge[i].w1]; //转移，注意判断j-edge[i].w>=0 
				if(j-edge[i].w2>=0) f2[v][j]|=f2[u][j-edge[i].w2];
			}
			if(--ind[v]==0) q.push(v);
		}
	}
	for(rint i=0;i<=10000;++i)
		if(f1[n][i]&&f2[n][i]){
			printf("%d",i); //输出
			return 0;
		}
	printf("IMPOSSIBLE"); //判断无解情况
	return 0;
}