给一个有向图，每条边有边权w,第k次经过一条边获得max(0,w−1−2−..−(k−1)),问最大获得权值。
显然一个点强联通分量里的点可以一次取走，对原图缩点，跑DAG.
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <cstdlib>
#include <queue>
#include <stack>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=Pre[x];p;p=Next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=Next[p])
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pi pair<int,int>
#define SI(a) ((a).size())
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
#define MAXN (2000010+10)
vi G[MAXN];
vector<ll> Gw[MAXN];
int pre[MAXN],lowlink[MAXN],sccno[MAXN],dfs_clock,scc_cnt;
stack<int> S;
void dfs(int u) {
pre[u] = lowlink[u] = ++dfs_clock;
S.push(u);
int sz=SI(G[u]);
Rep(i,sz) {
int v=G[u][i];
if (!pre[v]) {
dfs(v);
lowlink[u]=min(lowlink[u],lowlink[v]);
} else if (!sccno[v]) {
lowlink[u]=min(lowlink[u],pre[v]);
}
}
if (lowlink[u]==pre[u]) {
scc_cnt++;
while(1) {
int x=S.top();S.pop();
sccno[x]=scc_cnt;
if (x==u) break;
}
}
}
void find_scc(int n) {
dfs_clock = scc_cnt = 0;
MEM(sccno)
MEM(pre)
Rep(i,n) if (!pre[i]) dfs(i);
}
ll value[MAXN]={};
ll calc(ll wei){
ll k=(long long)(sqrtl((long double)wei*2+0.25)-0.5);
return (k*(6*wei-(k+1)*(k+2)))/6+wei;
}
vi G2[MAXN];
vector<ll> G2w[MAXN];
ll f[MAXN];
#define gmax(a,b) a=max(a,b)
struct DFS{
int n,vis[MAXN];
vi e[MAXN];
bool b[MAXN];
void init(int n) {
memset(vis,0,sizeof(int)*(n+1));
}
void addedge(int u,int v) {
e[u].pb(v);
}
ll dfs(int s) {
if (vis[s]) return f[s];
f[s]=value[s];
Rep(i,SI(e[s])) {
gmax(f[s],dfs(e[s][i])+G2w[s][i]+value[s]);
}
vis[s]=1;
return f[s];
}
}S1;
int main() {
// freopen("E.in","r",stdin);
int n=read(),m=read();
For(i,m) {
int x=read(),y=read(),w=read();
x--,y--;
G[x].pb(y);
Gw[x].pb(w);
}
find_scc(n);
ll ans=0;
S1.init(scc_cnt);
Rep(i,n) {
Rep(j,SI(G[i])) {
int v=G[i][j];ll w=Gw[i][j];
if (sccno[i]==sccno[v]) {
if (w==0) continue;
ll totw=calc(w);
value[sccno[i]]+=totw;
}else {
S1.addedge(sccno[i],sccno[v]);
G2w[sccno[i]].pb(w);
}
}
}
int s=read();
s=sccno[--s];
S1.dfs(s);
cout<<f[s]<<endl;
return 0;
}