SPFA60/80求助
  • 板块P2648 赚钱
  • 楼主Jessica2333
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/12/20 13:09
  • 上次更新2023/10/28 14:01:20
查看原帖
SPFA60/80求助
444063
Jessica2333楼主2021/12/20 13:09

先说一下疑惑:把初始MMMAX(int类型)设为-2147483647是60分;把初始MMMAX(int类型)设置成超出int范围的负数就得80分???

大大的疑惑

玄学问题啊各位大佬们救救孩子吧

#include<bits/stdc++.h>
using namespace std;
long long vist[10001],head[10001],num=1,cont[10001],c,dist[10001],flag=0,d;
int MMMAX=-2147483647;
struct Edge{
	long long next,end;
	long long v;
}m[10001];
void add_edge(long long st,long long end,long long v)
{
	m[num].v=v;
	m[num].end=end;
	m[num].next=head[st];
	head[st]=num++;
}
void SPFA(long long u)
{
	long long temp,i,v,e;
	queue<int> q;
	for(i=1;i<=c;i++) dist[i]=MMMAX;
	dist[u]=d;
	cont[u]=1;
	q.push(u);
	vist[u]=1;
	while(!q.empty())
	{
		temp=q.front();//选头的点,将这个点对有关的点做刷新
		q.pop();//出队
		vist[temp]=0;//标记(提高效率) 
		for(i=head[temp];i!=0;i=m[i].next)//遍历以temp为起点的其他路 
		{
			e=m[i].end;//存一个终点 
			if(dist[e]<dist[temp]+m[i].v&&dist[temp]!=-2147483647)//头的点的改变是否会对到e 的点有影响 
			{
				dist[e]=dist[temp]+m[i].v;
				if(vist[e]!=1)//若dist[e]不在队列里 
				{
					if(++cont[e]>=c)
					{
						flag=1;
						return ;
					}
					vist[e]=1;
					q.push(e);
				}				
			}
		}
	}
}
int main()
{
	long long i,j,p,f,u,v,w,final,ans;
	cin>>d>>p>>c>>f;
	for(i=1;i<=p;i++)
	{
		cin>>u>>v;
		add_edge(u,v,d);
	}
	for(i=1;i<=f;i++)
	{
		cin>>u>>v>>w;
		add_edge(u,v,d-w);
	}
	final=MMMAX;
	ans=MMMAX;
	for(i=1;i<=c;i++)
	{
		SPFA(i);
		if(flag==1) break;
		for(j=1;j<=c;j++)
		{
			ans=max(dist[j],ans);
		}
		final=max(ans,final);
	}
    if(flag==0) cout<<final;
    else cout<<"orz";
    
}
2021/12/20 13:09
加载中...