题目：采蘑菇

70分代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int m,n,x[MAXN],y[MAXN],sum[MAXN],cs[MAXN],dp[MAXN],u[MAXN],s;
int dfn[MAXN],low[MAXN],bj[MAXN],zh[MAXN],len,sl;
double hf[MAXN];
map<int,int> pr[MAXN];
stack<int> q;
queue<int> w;
vector<int> g[MAXN],p[MAXN];
void tarjan(int x)
{
	dfn[x]=low[x]=++len;
	zh[x]=1;
	q.push(x);
	for(int i=0;i<g[x].size();i++)
		if(!dfn[g[x][i]])
		{
			tarjan(g[x][i]);
			low[x]=min(low[x],low[g[x][i]]);
		}
		else if(zh[g[x][i]])low[x]=min(low[x],low[g[x][i]]);
	if(dfn[x]==low[x])
	{
		sl++;
		while(q.top()!=x)
		{
			bj[q.top()]=sl;
			zh[q.top()]=0;
			q.pop();
		}
		bj[q.top()]=sl;
		zh[q.top()]=0;
		q.pop();
	}
}
int dijkstra(int x)
{
	memset(dp,128,sizeof(dp));
	int k=0;
	dp[x]=sum[x];
	u[x]=1;
	w.push(x);
	while(!w.empty())
	{
		x=w.front();
		w.pop();
		u[x]=0;
		k=max(k,dp[x]);
		for(int i=0;i<p[x].size();i++)
			if(dp[x]+pr[x][p[x][i]]+sum[p[x][i]]>dp[p[x][i]])
			{
				dp[p[x][i]]=dp[x]+pr[x][p[x][i]]+sum[p[x][i]];
				if(!u[p[x][i]])
				{
					u[p[x][i]]=1;
					w.push(p[x][i]);
				}
			}
	}
	return k;
}
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i]>>y[i]>>cs[i]>>hf[i];
		g[x[i]].push_back(y[i]);
	}
	for(int i=1;i<=m;i++)
		if(!dfn[i])tarjan(i);
	for(int i=1;i<=n;i++)
		if(bj[x[i]]==bj[y[i]])
		{
			hf[i]*=10;
			while(cs[i])sum[bj[x[i]]]+=cs[i],cs[i]=cs[i]*int(hf[i])/10;
		}
		else pr[bj[x[i]]][bj[y[i]]]=cs[i];
	for(int i=1;i<=m;i++)
		for(int j=0;j<g[i].size();j++)
			if(bj[i]!=bj[g[i][j]])p[bj[i]].push_back(bj[g[i][j]]);
	cin>>s;
	cout<<dijkstra(bj[s]);
	return 0;
}