rt 玄关

提交记录

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=8e4+5,M=2e5+5;
struct graph {
    struct enode {
    	int nxt,to,val,heal;
    } edge[M];
    int tot,head[N];
    void add(int u,int v,int x,int y) {
		edge[++tot]={head[u],v,x,y};
    	head[u]=tot;
    }   
} G,T;
int n,m;
int low[N],dfn[N],cnt,st[N],top,idx,bel[N];
bool ins[N];
void tarjan(int u) {
    low[u]=dfn[u]=++cnt;
    st[++top]=u;
    ins[u]=1;
    for(int i=G.head[u];i;i=G.edge[i].nxt) {
        int v=G.edge[i].to;
        if(!dfn[v]) {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(ins[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]) {
        idx++;
        int v=0;
        do {
            v=st[top--];
            ins[v]=0;
            bel[v]=idx;
        } while(v!=u);
    }
}
int c[N],ind[N],dp[N];
queue<int> q;
void topsort() {
    for(int i=1;i<=idx;i++)
        if(!ind[i]) q.push(i);
    // cout<<"in topsort(): q.size()="<<q.size()<<'\n';
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        dp[u]+=c[u];
        for(int i=T.head[u];i;i=T.edge[i].nxt) {
            int v=T.edge[i].to,w=T.edge[i].val;
            dp[v]=max(dp[v],dp[u]+w);
            if(!--ind[v]) q.push(v);
        }
    }
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++) {
		int u,v,x;
		double y;
		cin>>u>>v>>x>>y;
		G.add(u,v,x,int(round(y*10)));
	}
	for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    // for(int i=1;i<=n;i++) cout<<bel[i]<<' ';
    // cout<<'\n';
    // for(int i=1;i<=idx;i++) cout<<c[i]<<' ';
    // cout<<'\n';
    for(int i=1;i<=n;i++) {
        for(int j=G.head[i];j;j=G.edge[j].nxt) {
            int v=G.edge[j].to,w=G.edge[j].val;
            if(bel[i]==bel[v]) {
                while(w) {
                    c[bel[i]]+=w;
                    (w*=G.edge[i].heal)/=10;
                }
            }
            else {
                T.add(bel[v],bel[i],w,0);
                ind[bel[i]]++;
            }
        }
    }
    // for(int i=1;i<=idx;i++) {
    //     cout<<i<<'\n';
    //     for(int j=T.head[i];j;j=T.edge[j].nxt)
    //         cout<<T.edge[j].to<<' '<<T.edge[j].val<<'\n';
    // }
    // for(int i=1;i<=idx;i++) cout<<dp[i]<<' ';
    // cout<<'\n';
    // for(int i=1;i<=idx;i++) cout<<ind[i]<<' ';
    // cout<<'\n';
    topsort();
    int s;
    cin>>s;
    cout<<dp[bel[s]]<<'\n';
	return 0;
}