60points help

回复帖子

@刘兆洲 2019-03-15 22:08 回复
#include <bits/stdc++.h>
#include <queue>
#include <set>
#include <vector>
#include <deque>

#define lowbit(x) x & -x

#pragma GCC optimize(3)

using namespace std;

inline char gc(void)
{
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}

template <class T> inline void read(register T &x)
{
    register long long flag = 1;
    x = 0; register char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') flag = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    x *= flag; return;
}

template <class T> inline void write(register T x)
{
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

template <class T> inline void writeln(register T x)
{
    write(x);
    puts("");
}

template <class T> inline void writeln(register T x, char c)
{
    putchar(c); write(x);
}

template <class T> inline void chkmax(T &X, const T Y)
{
    X > Y ? X = X : X = Y;
}

template <class T> inline void chkmin(T &X, const T Y)
{
    X < Y ? X = X : X = Y;
}

typedef long long ll;
typedef unsigned long long ull;

enum {
    maxn = 500010
};

class Edge {
    public:
        int to, val, next;
        inline void init(int _t, int _v, int _n) {
            to = _t; val = _v; next = _n; return;
        }
} line[maxn];

int head[maxn], cnt = 0, e;

inline void add(int u, int v, int w) {
    line[++cnt].init(v, w, head[u]);
    head[u] = cnt; return;
}

int dis[maxn]; bool vis[maxn];

inline bool spfa(int dep) {
    vis[dep] = true;
    for (e = head[dep]; e; e = line[e].next)
    {
        int u = line[e].to, v = line[e].val;
        if (dis[u] < dis[dep] + v) {
            dis[u] = dis[dep] + v;
            if (vis[u]) return false;
            if (!spfa(u)) return false;
        }
    } 
    vis[dep] = false; return true;
}

int n, m, opt;

int main(void)
{
    read(n); read(m);
    for (register int i = 1; i <= m; i++) {
        read(opt); int x, y, z;
        read(x); read(y); if (opt != 3) read(z);
        if (opt == 1) add(y, x, z);
        if (opt == 2) add(x, y, -z);
        if (opt == 3) add(x, y, 0), add(y, x, 0);
    }

    for (register int i = 1; i <= n; i++)
        dis[i] = - (1 << 30), add(0, i, 0);

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

    return 0;
}