작은 K 농장

링크
　　http://www.lydsy.com/JudgeOnline/problem.php?id=3436
해제
물 문 제 를 풀 고 긴 장 된 신경 을 풀다.계차 구속 건 도 최 장 거리.뭐? 이렇게 많아?첫 번 째 는 DFS 버 전의 spfa, 두 번 째 는 BFS 버 전의 spfa 다.
코드

//    
#include 
#include 
#include 
#define maxn 100000
using namespace std;
int N, M, head[maxn], to[maxn], cnt[maxn], w[maxn], vis[maxn], nex[maxn], dist[maxn],
    tot, ans;
inline void adde(int a, int b, int v)
{to[++tot]=b;w[tot]=v;nex[tot]=head[a];head[a]=tot;}
bool spfa(int pos)
{
    int p;
    vis[pos]=1;
    for(p=head[pos];p;p=nex[p])
    {
        if(dist[to[p]]if(vis[to[p]])return false;
            if(!spfa(to[p]))return false;
        }
    }
    vis[pos]=0;
    return true;
}
int main()
{
    int i, a, b, c, type;
    scanf("%d%d",&N,&M);
    for(i=1;i<=M;i++)
    {
        scanf("%d%d%d",&type,&a,&b);
        if(type==3){adde(a,b,0),adde(b,a,0);continue;}
        scanf("%d",&c);
        if(type==2)swap(a,b),c=-c;
        adde(a,b,c);
    }
    for(i=1;i<=N;i++)
    {
        if(!spfa(i))
        {
            printf("No");
            return 0;
        }   
    }
    printf("Yes");
    return 0;
}