1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102
| #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <cctype> #include <vector> #include <queue> #include <utility> #define ri register int #define ll long long #define ull unsigned long long #define pb push_back #define DEBUG freopen("dat.in","r",stdin);freopen("wa.out","w".stdout); #define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);} #define SIZE 23333 using std::min; using std::max; using std::pair; using std::queue; using std::priority_queue; using std::vector; inline char gc(){ static char buf[SIZE],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++; } template <class T>inline void read(T &x){ x=0;int ne=0;char c; while((c=getchar())>'9'||c<'0')ne=c=='-';x=c-48; while((c=getchar())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ; } const int maxn=500005; const int inf=0x7fffffff; struct O_Edge{int ne,to,dis,val;}oe[maxn<<1]; int oh[maxn],oenum=1; inline void oa_edge(int f,int to,int c,int v){oe[++oenum].ne=oh[f],oe[oenum].to=to,oe[oenum].dis=c,oe[oenum].val=v,oh[f]=oenum;} struct S_Edge{int ne,to,dis;}se[maxn<<1]; int sh[maxn],senum=1; inline void sa_edge(int f,int to,int c){se[++senum].ne=sh[f],se[senum].to=to,se[senum].dis=c,sh[f]=senum;} ll w[maxn]; int n,m,in_scc[maxn],cnt=0; int dfn[maxn],low[maxn],tot=0,st[maxn],top=0; bool siv[maxn],vis[maxn]; void tarjan(int now){ int v;dfn[now]=low[now]=++tot,st[++top]=now,siv[now]=1; for(ri i=oh[now];i;i=oe[i].ne){ v=oe[i].to; if(!dfn[v]){tarjan(v);low[now]=min(low[now],low[v]);} else if(siv[v])low[now]=min(low[now],low[v]); } if(dfn[now]==low[now]){ cnt++; do{v=st[top--],siv[v]=0,in_scc[v]=cnt;}while(now!=v); } } typedef pair<ll,int> pii; int s;ll dis[maxn],ans=0; void dij(){ int u,v;priority_queue <pair<ll,int> >q; dis[s]=w[s],q.push(pii(-dis[s],s)); while(q.size()){ u=q.top().second;q.pop(); if(vis[u])continue;vis[u]=1; for(ri i=sh[u];i;i=se[i].ne){ v=se[i].to; if(dis[v]<dis[u]+se[i].dis){dis[v]=dis[u]+se[i].dis,q.push(pii(-dis[v],v));} } } return ; } int main(){ int x,y,z,zz,num;double p; read(n),read(m); for(ri i=1;i<=m;i++){ read(x),read(y),read(z);scanf("%lf",&p);zz=z,num=0; while(zz){num+=zz,zz*=p;} oa_edge(x,y,z,num); } for(ri i=1;i<=n;i++)if(!dfn[i])tarjan(i); for(ri i=1;i<=n;i++){x=in_scc[i]; for(ri j=oh[i];j;j=oe[j].ne){ y=in_scc[oe[j].to]; if(x==y)w[x]+=oe[j].val; } } for(ri i=1;i<=n;i++){x=in_scc[i]; for(ri j=oh[i];j;j=oe[j].ne){ y=in_scc[oe[j].to]; if(y!=x){sa_edge(x,y,w[y]+oe[j].dis);} } } read(s);s=in_scc[s];dij(); for(ri i=1;i<=cnt;i++)ans=max(ans,dis[i]); printf("%lld\n",ans); return 0; }
|