题意：

　　给一个混合图，求判断是否有负环的存在，若有，输出YES，否则NO。有重边。

思路：

　　这是spfa的功能范围。一个点入队列超过n次就是有负环了。因为是混合图，所以当你跑一次spfa时发现没有负环，但是负环仍可能存在，因为有向边！

　　但是单源最短路也有起点啊，难道穷举起点？不用，负环是必须有某些边是带负权的，那么我们只要穷举负权边的起点就行了，因为单单跑一次spfa不能保证能遍历所有点，但是如果穷举负权边起点还没有找到负环，那么负环不可能存在（剩下的都是正权，怎么可能有负环）。

 

1 //#include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #define LL long long 8 #define pii pair
            
              9 #define INF 0x7f7f7f7f10 using namespace std;11 const int N=550;12 int n, m, edge_cnt;13 vector
             
               vect[N];14 struct node15 {16 int from, to, val;17 node(){};18 node(int f,int t,int v):from(f),to(t),val(v){};19 }edge[600000];20 21 22 void add_node(int from,int to,int val)23 {24 edge[edge_cnt]=node(from,to,val);25 vect[from].push_back(edge_cnt++);26 }27 28 int dis[N], inq[N], cnt[N];29 int spfa(int s)//模板30 {31 memset(inq,0,sizeof(inq));32 memset(cnt,0,sizeof(cnt));33 memset(dis,0x7f,sizeof(dis));34 deque
              
                que(1,s);35 inq[s]=1;36 dis[s]=0;37 38 while(!que.empty())39 {40 int x=que.front();41 que.pop_front();42 inq[x]=0;43 for(int i=0; i
               
                dis[x]+e.val)47 {48 dis[e.to]=dis[x]+e.val;49 if(!inq[e.to])50 {51 if(++cnt[e.to]>n) return false;52 inq[e.to]=1;53 que.push_back(e.to);54 }55 }56 }57 }58 return true;59 }60 61 int main()62 {63 freopen("input.txt", "r", stdin);64 int a, b, c, t, w;65 cin>>t;66 while(t--)67 {68 scanf("%d%d%d",&n,&m,&w);69 edge_cnt=0;70 memset(edge,0,sizeof(edge));71 for(int i=0; i<=n; i++) vect[i].clear();72 73 for(int i=0; i
                

ver;80 for(int i=0; i