自动搬运

查看原文

来自洛谷，原作者为

	Dehydration 临时主页：https://www.luogu.com.cn/paste/22qa5kjy

搬运于2025-08-24 21:27:55，当前版本为作者最后更新于2023-07-13 14:58:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言：

绿题就是绿题，做出来也得十几分钟。

看一下居然是最优解！

Problem。

最优解提交记录。

思路和代码：

首先我就想到了动态规划：

设 $dp_{i1}$ 表示起点到 $i$ 点总共需要花费的。

设 $dp_{i0}$ 表示起点到 $i$ 点的总方案数。

说句题外话：我首先没想到要搞方案数，死了五分钟。

则如果从 $x$ 走到 $y$ 而且他们之间代价为 $money$ 可得出：

$dp_{y0}=dp_{x0}+dp_{y0}$。

$dp_{y1}=dp_{y1}+dp_{x1}+dp_{x0}\times money$。

第一个很简单理解，这是因为方案数为累加，运用加法原理。

第二个是将两点的总价值相加，再加上方案数乘上代价，这是因为一共有方案数个方案，这条线也需走方案数个，需相乘再相加。

于是愉快地得出错误代码：

//20pts
//luogu P1685
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int dp[N][2],n,m,qi,zh,p;
struct DO
{
    int next;
    int to;
    int money;
};
const int maxn=5e4+5; 
DO a[maxn];
int head[maxn],cnt=1;
void add(int x,int y,int sum)
{
    a[cnt].to=y;
    a[cnt].money=sum;
    a[cnt].next=head[x];
    head[x]=cnt++;
}
void DP(int x)
{
	for(int i=head[x];i;i=a[i].next)
	{
		int y=a[i].to;
		dp[y][0]=(dp[x][0]+dp[y][0])%10000;
		dp[y][1]=(dp[y][1]+dp[x][1]+dp[x][0]*a[i].money)%10000;
		DP(y);
	}
}
int main()
{
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>qi>>zh>>p; 
	for(int i=1;i<=m;i++)
	{
		int x,y,sum;
		cin>>x>>y>>sum;
		add(x,y,sum);
	}
	dp[qi][0]=1;
	DP(qi);
	cout<<((dp[zh][0]-1)*p+dp[zh][1])%10000;
} 

绿+红+黑。

我们发现，直接搜到这点继续往下搜有可能信息不全，会错误，而且搜那么多次，很显然会超时，为了预防这些，我们可以记录点的入度，如果入读为零即可安心往下搜。

于是我们修改函数和输入，得出最优解：

//100pts
//luogu P1685
//最优解（用快读+关闭输出流的cout
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int dp[N][2],n,m,qi,zh,p;
int in[N];
struct DO
{
    int next;
    int to;
    int money;
};
typedef int LL;
inline LL read()
{
	register LL x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
const int maxn=5e4+5; 
DO a[maxn];
int head[maxn],cnt=1;
void add(int x,int y,int sum)
{
    a[cnt].to=y;
    a[cnt].money=sum;
    a[cnt].next=head[x];
    head[x]=cnt++;
}
void DP(int x)
{
	for(int i=head[x];i;i=a[i].next)
	{
		int y=a[i].to;
		dp[y][0]=(dp[x][0]+dp[y][0])%10000;
		dp[y][1]=(dp[y][1]+dp[x][1]+dp[x][0]*a[i].money)%10000;
		in[y]--;
		if(!in[y])DP(y);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	n=read(),m=read(),qi=read(),zh=read(),p=read();
	for(int i=1;i<=m;i++)
	{
		int x,y,sum;
		x=read(),y=read(),sum=read(),in[y]++;
		add(x,y,sum);
	}
	dp[qi][0]=1;
	DP(qi);
	cout<<((dp[zh][0]-1)*p+dp[zh][1])%10000;
} 

如果觉得这个有用，那就点赞顶这篇题解，谢谢！