P1685 游览
Dehydration
·
·
题解
前言：
绿题就是绿题，做出来也得十几分钟。
看一下居然是最优解！
Problem。
最优解提交记录。
思路和代码：
首先我就想到了动态规划：
设 dp_{i1} 表示起点到 i 点总共需要花费的。
设 dp_{i0} 表示起点到 i 点的总方案数。
说句题外话：我首先没想到要搞方案数，死了五分钟。
则如果从 x 走到 y 而且他们之间代价为 money 可得出：
$dp_{y1}=dp_{y1}+dp_{x1}+dp_{x0}\times money$。
第一个很简单理解，这是因为方案数为累加，运用加法原理。
第二个是将两点的总价值相加，再加上方案数乘上代价，这是因为一共有方案数个方案，这条线也需走方案数个，需相乘再相加。
于是愉快地得出错误代码：
```c++
//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;
}
```
如果觉得这个有用，那就点赞顶这篇题解，谢谢！