求调

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 2e5+5;
int n,m,root;
struct road
{
	int to,num;
	double k;
};
vector <road> G[maxn];
int dfn[maxn],low[maxn],dfncnt,scc[maxn],scccnt;
bool in_stack[maxn];
stack <int> s;
void dfs(int u)
{
	dfn[u] = low[u] = ++dfncnt;
	in_stack[u] = true;
	s.push(u);
	for(auto v : G[u])
	{
		if(!dfn[v.to])
		{
			dfs(v.to);
			low[u] = min(low[u],low[v.to]);
		}
		else
		{
			if(in_stack[v.to])
			{
				low[u] = min(low[u],dfn[v.to]);
			}
		}
	}
	if(dfn[u] == low[u])
	{
		scccnt++;
		while(s.top() != u && !s.empty())
		{
			scc[s.top()] = scccnt;
			in_stack[s.top()] = false;
			s.pop();
		}
		if(!s.empty())
		{
			scc[u] = scccnt;
		    in_stack[u] = false;
		    s.pop();
		}
	}
}
int nn,val[maxn],sum,x;
vector <road> nG[maxn];
set <pair <pair<int, int > ,pair<int, double > > > st;
void build()
{
	nn = scccnt;
	for(int u = 1; u <= n; u++)
	{
		for(auto v : G[u])
		{
			int nu = scc[u],nv = scc[v.to];
			if(nu != nv)
			{
				st.insert({ {nu,nv}, {v.num,v.k} } );
			}
			else
			{
				sum = 0,x = v.num;
				while(x > 0)
				{
					sum+=x;
					x*=v.k;
				}
				val[nu]+=sum;
			}
		}
	}
	for(auto g : st)
	{
		nG[g.first.first].push_back({g.first.second,g.second.first,g.second.second});
	}
}
int ans[maxn];
bool vis[maxn];
void spfa()
{
	queue <int> Q;
	memset(ans,0,sizeof(ans));
	memset(vis,0,sizeof(vis));
	ans[root] = val[root];
	vis[root] = 1;
	Q.push(root);
	while(!Q.empty())
	{
		int u = Q.front();
		Q.pop();
		vis[u] = 0;
		for(auto v : nG[u])
		{
			if(ans[u] + v.num + val[v.to] > ans[v.to])
			{
				ans[v.to] = ans[u] + v.num + val[v.to];
				if(!vis[v.to])
				{
					Q.push(v.to);
					vis[v.to] = 1;
				}
			}
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >>n>>m;
	int u,v,snum;
	double kk;
	for(int i = 1; i <= m; i++)
	{
		cin >>u>>v>>snum>>kk;
		G[u].push_back({v,snum,kk});
	}
	cin >>root;
	dfs(1);
	build();
	root = scc[root];
	spfa();
	int maxn = -1;
	for(int i = 1; i <= nn; i++)
	{
		maxn = max(maxn,ans[i]);
	}
	cout <</*"\n"<<*/maxn;
}