计蒜客-时光机

2019-08-06

蒜头君生活的宇宙有 n 个星球，有 m 条虫洞。蒜头君发明了时光机，利用虫洞进行时光旅行。这 m 条虫洞，第 i条虫洞能实现星球 a_i 到 b_i 的单向旅行。蒜头君发明的时光机不稳定，通过第 i 条虫洞能够使得时间前进或者倒退 c_i（c_i≥0 表示前进，c_i < 0 表示倒退）。

如果通过时光机能够让时间无限倒退，那么将会掉进时间漩涡，从而实现穿越。那么蒜头君发明的时光机能否实现穿越（蒜头君可以从任何星球开始）。

输入格式

输入第一行两个整数n(1≤n≤1000)，m(1≤m≤10000)。

接下来 m 行，第 i 每行输入 3 个整数 a_i, b_i (1≤a_i,b_i≤n)，c_i (−10000≤c_i≤10000)，表示一个虫洞。

输出格式

如果蒜头君能实现穿越，输出"Yes"，否则输出"No"。

样例输入

样例输出

Yes

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

const int N = 1001;
const int M = 10001;

struct edge {
    int v, w, next;
    edge() {}
    edge(int _v, int _w, int _next) : v(_v), w(_w), next(_next) {}
} E[M << 1];

int p[N];
int eid;

void init() {
    memset(p, -1, sizeof p);
    eid = 0;
}

void insert(int u, int v, int w) {
    E[eid] = edge(v, w, p[u]);
    p[u] = eid++;
}

int dis[N];
int cnt[N];
bool vis[N];
queue<int> q;
int n, m;


bool spfa(int s) {
    memset(dis, 0x3f, sizeof dis);
    memset(vis, false, sizeof vis);
    memset(cnt, 0, sizeof cnt);
    dis[s] = 0;
    vis[s] = true;
    q.push(s);
    cnt[s] = 1;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;

        for (int e = p[u]; e != -1; e = E[e].next) {
            int v = E[e].v;
            int w = E[e].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                    cnt[v]++;
                    if (cnt[v] > n) {
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    int a, b, c;
    init();
    while (m--) {
        cin >> a >> b >> c;
        insert(a, b, c);
    }

    for (int i = 1; i <= n; i++) { //设置一个辅助顶点单向连接所有顶点,这样这样就不用多次SPFA了
        insert(0, i, 0);
    }

    if (spfa(0)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}