【题解】LuoGu3116：[USACO15JAN]约会时间Meeting Time

本文链接：https://blog.csdn.net/ModestCoder_/article/details/95944520

博客给出原题传送门，介绍在拓扑图上进行动态规划（DP）的解题方法。定义f[u][i]和g[u][i]分别表示贝茜和爱丽丝是否能跑到点u且距离为i，一边拓扑一边做DP，转移方程见代码，最后从小到大枚举答案，若都不符合则输出impossible。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

原题传送门
拓扑上跑dp
$f [u] [i] 表示贝茜是否能跑到点 u ，距离为 i$
$g [u] [i] 同理，表示爱丽丝$
一边拓扑，一边做dp
转移方程见代码

最终从小到大枚举答案是否符合
都不符合impossible

Code :

#include <bits/stdc++.h>
#define maxn 110
#define maxlen 10010
using namespace std;
struct Edge{
	int to, next, len1, len2;
}edge[maxlen];
int num, head[maxn], in[maxn], n, m, f[maxn][maxlen], g[maxn][maxlen];
queue <int> q;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void addedge(int x, int y, int z1, int z2){ edge[++num] = (Edge) { y, head[x], z1, z2}; head[x] = num; }

int main(){
	n = read(), m = read();
	for (int i = 1; i <= m; ++i){
		int x = read(), y = read(), z1 = read(), z2 = read();
		addedge(x, y, z1, z2);
		++in[y];
	}
	f[1][0] = g[1][0] = 1;
	for (int i = 1; i <= n; ++i) if (!in[i]) q.push(i);
	while (!q.empty()){
		int u = q.front(); q.pop();
		for (int i = head[u]; i; i = edge[i].next){
			int v = edge[i].to;
			for (int j = 0; j + edge[i].len1 < maxlen; ++j) f[v][j + edge[i].len1] |= f[u][j];
			for (int j = 0; j + edge[i].len2 < maxlen; ++j) g[v][j + edge[i].len2] |= g[u][j];
			if (!(--in[v])) q.push(v);
		}
	}
	for (int i = 0; i < maxlen; ++i)
		if (f[n][i] && g[n][i]){
			printf("%d\n", i); return 0;
		}
	printf("IMPOSSIBLE");
	return 0;
}