[luoguP1993] 小 K 的农场（差分约束 + spfa 判断负环）

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #define N 100001

 int n, m, cnt;

 int head[N], to[N << ], val[N << ], next[N << ], dis[N];

 bool vis[N];

 inline int read()

 {

     int x = , f = ;

     char ch = getchar();

     for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;

     for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';

     return x * f;

 }

 inline void add(int x, int y, int z)

 {

     to[cnt] = y;

     val[cnt] = z;

     next[cnt] = head[x];

     head[x] = cnt++;

 }

 inline bool spfa(int u)

 {

     int i, v;

     vis[u] = ;

     for(i = head[u]; i ^ -; i = next[i])

     {

         v = to[i];

         if(dis[v] > dis[u] + val[i])

         {

             dis[v] = dis[u] + val[i];

             if(vis[v]) return ;

             else if(!spfa(v)) return ;

         }

     }

     vis[u] = ;

     return ;

 }

 int main()

 {

     int i, j, opt, x, y, z;

     n = read();

     m = read();

     memset(head, -, sizeof(head));

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

     {

         opt = read();

         x = read();

         y = read();

         if(opt == ) add(x, y, ), add(y, x, );

         else

         {

             z = read();

             if(opt == ) add(x, y, -z);

             if(opt == ) add(y, x, z);

         }

     }

     memset(dis,  / , sizeof(dis));

     for(i = ; i <= n; i++) add(, i, );

     dis[] = ;

     spfa() ? puts("Yes") : puts("No");

     return ;

 }