【SPFA判断负环】BZOJ1715- [Usaco2006 Dec]Wormholes 虫洞

 #include<bits/stdc++.h>

 using namespace std;

 struct edge

 {

     int to,len;

 };

 const int MAXN=+;

 vector<edge> E[MAXN];

 int f,n,m,w;

 int vis[MAXN],dis[MAXN],flag;

 void addedge(int s,int e,int t)

 {

     E[s].push_back((edge){e,t});

 }

 void init()

 {

     scanf("%d%d%d",&n,&m,&w);

     for (int i=;i<MAXN;i++) vector<edge>().swap(E[i]);

     for (int i=;i<=m;i++)

     {

         int s,e,t;

         scanf("%d%d%d",&s,&e,&t);

         addedge(s,e,t);

         addedge(e,s,t);

     }

     for (int i=;i<=w;i++)

     {

         int s,e,t;

         scanf("%d%d%d",&s,&e,&t);

         addedge(s,e,-t);

     }

 }

 void spfa(int u)

 {

     if (vis[u])

     {

         flag=;

         return;

     }

     vis[u]=;

     for (int i=;i<E[u].size();i++)

     {

         int to=E[u][i].to,len=E[u][i].len;

         if (dis[to]>dis[u]+len)

         {

             dis[to]=dis[u]+len;

             spfa(to);

             if (flag) return;

         }

     }

     vis[u]=;

 }

 void solve()

 {

     memset(vis,,sizeof(vis));

     flag=;

     for (int i=;i<=n;i++)

     {

         spfa(i);

         if (flag) break;

     }

     puts(flag?"YES":"NO");

 }

 int main()

 {

     scanf("%d",&f);

     while (f--)

     {

         init();

         solve();

     }

     return ;

 }