先说一下疑惑:把初始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";
}