30WA 玄关求调
  • 板块P2656 采蘑菇
  • 楼主xianxi
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/12/19 13:19
  • 上次更新2024/12/19 20:05:22
查看原帖
30WA 玄关求调
1021348
xianxi楼主2024/12/19 13:19
#include<bits/stdc++.h>
using namespace std;
const int maxn=800005;
struct node{
	int v,w;
};
int n,dfn[maxn],p[maxn],dis[maxn],m,low[maxn],t,cnt[maxn],num,S;
bool vis[maxn];
map<int,map<int,int> >d;
map<int,map<int,int> >arr;
vector<int>f[maxn];
vector<node>s[maxn];
stack<int>q; 
void tarjan(int k)
{
	q.push(k);
	vis[k]=1;
	low[k]=dfn[k]=++t;
	for(int i=0;i<f[k].size();++i)
	{
		int v=f[k][i];
		if(!dfn[v])
		{
			tarjan(v);
			low[k]=min(low[v],low[k]);
		}
		else if(vis[v])
		{
			low[k]=min(low[k],dfn[v]);
		}
	}
	if(dfn[k]==low[k])
	{
		num++;
		while(1)
		{
			int u=q.top();
			q.pop();
			vis[u]=0;
			cnt[u]=num;
			if(u==k)break;
		}
	}
	return ;
}
void spfa()
{
	queue<int>qq;
	dis[S]=p[S];
	vis[S]=1;
	qq.push(S);
	int nn;
	while(!qq.empty())
	{
		nn=qq.front();
		vis[nn]=0;
		qq.pop();
		for(int i=0;i<s[nn].size();++i)
		{
			int ii=s[nn][i].v,val=s[nn][i].w;
			if(dis[ii]<dis[nn]+val+p[ii])
			{
				dis[ii]=dis[nn]+val+p[ii];
				if(vis[ii]==0)
				{
					vis[ii]=1;
					qq.push(ii);
				}
			}
		}
	}
	return ;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;++i)
	{
		int aa,bb,dd;
		double cc;
		cin>>aa>>bb;
		cin>>dd>>cc;
		arr[aa][bb]=dd;
		d[aa][bb]=cc*10;
		f[aa].push_back(bb); 
	}
	cin>>S;
	for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i);
	for(int i=1;i<=n;++i)
	{
		for(int j=0;j<f[i].size();++j)
		{
			if(cnt[i]!=cnt[f[i][j]])
			{
				s[cnt[i]].push_back({cnt[f[i][j]],arr[i][f[i][j]]});//可以有重边
			}
			else
			{
				while(arr[i][f[i][j]])
				{
					p[cnt[i]]+=arr[i][f[i][j]];
					arr[i][f[i][j]]=arr[i][f[i][j]]*d[i][f[i][j]]/10.0;
				}
			}
		}
	}
	memset(vis,0,sizeof vis);
	S=cnt[S];
	spfa(); 
	int ans=0;
	for(int i=1;i<=num;++i)ans=max(dis[i],ans);
	cout<<ans;
	return 0;
}
2024/12/19 13:19
加载中...