P1993-小K的农场

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define pb push_back
 4 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
 5 #define INF 0x3f3f3f3f
 6 #define ll long long
 7 inline ll read()
 8 {
 9     ll ans = 0;
10     char ch = getchar(), last = ‘ ‘;
11     while(!isdigit(ch)) last = ch, ch = getchar();
12     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - ‘0‘, ch = getchar();
13     if(last == ‘-‘) ans = -ans;
14     return ans;
15 }
16 inline void write(ll x)
17 {
18     if(x < 0) x = -x, putchar(‘-‘);
19     if(x >= 10) write(x / 10);
20     putchar(x % 10 + ‘0‘);
21 }
22 #define maxn 10003
23 int n,m;
24 struct edge
25 {
26     int to;
27     int cost;
28 };
29 vector<edge> G[maxn];
30 int dis[maxn];
31 int vis[maxn];
32 bool find_negative_loop(int u)
33 {
34     vis[u] = 1;
35     for(int i = 0; i < G[u].size(); i ++)
36         if(dis[G[u][i].to] > dis[u] + G[u][i].cost)
37         {
38             dis[G[u][i].to] = dis[u] + G[u][i].cost;
39             if(vis[G[u][i].to]) 
40                 return true;
41             if(find_negative_loop(G[u][i].to)) 
42                 return true;
43         }
44     vis[u] = 0;
45     return false;
46 }
47 int main()
48 {
49     n = read();
50     m = read();
51 
52     _for(i,1,m+1)
53     {
54         int a,b,c,d;
55         a = read();
56         if(a==3)
57         {
58             b = read();
59             c = read();
60             G[b].pb({c,0}),G[c].pb({b,0});
61         }
62         else if(a==1)
63         {
64             b = read();
65             c = read();
66             d = read();
67             G[b].pb({c,-d});
68         }
69         else
70         {
71             b = read();
72             c = read();
73             d = read();
74             G[c].pb({b,d});
75         }
76     }
77 //    cout << G[1][0].to << " " << G[1][0].cost << endl;
78 //    cout << G[1][1].to << " " << G[1][1].cost << endl;
79     _for(i,1,n+1)
80         G[0].pb({i,0});
81     memset(dis,INF,sizeof(dis));
82     dis[0] = 0;
83     if(find_negative_loop(0))
84         printf("No\n");
85     else
86         printf("Yes\n");
87     return 0;
88 }