P1993-小K的农场_C

概述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 rea

 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 1000323 int n,m;24 struct edge25 {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         else70         {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,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     else86         printf("Yes\n");87     return 0;88 }