spfa判负环

如果一个点在spfa中被入队了大于n次

那么，我们就能肯定，有负环出现。

因为一个点入队时，他肯定被更新了一次。

所以........ 如果不存在负权环。这个点最多被更新节点数次

我们就可以利用这个性质判负环

亏我dijk写了一上午

语文模板题

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int dis[11000];struct L{    int point;    int weight;    int nxt;};L line[100000];int head[10000],tail;bool exist[100000];int inque[100000];queue
         
           q;int n,m;void add(int x,int y,int val){ line[++tail].point=y; line[tail].weight=val; line[tail].nxt=head[x]; head[x]=tail;}void spfa(int begin){ memset(dis,0x3f,sizeof(dis)); memset(exist,0,sizeof(exist)); dis[begin]=0; exist[begin]=true; inque[begin]+=1; q.push(begin); int pass; while(!q.empty()) { pass=q.front(); q.pop(); exist[pass]=false; if(inque[pass]>n) { printf("Forever love"); exit(0); } for(int need=head[pass];need;need=line[need].nxt) if(dis[pass]+line[need].weight