P1993-小K的农场

川长思鸟来 2023-06-01 08:55 17阅读 0赞

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 }

转载于:https://www.cnblogs.com/Asurudo/p/11533281.html