计蒜客-时光机
蒜头君生活的宇宙有 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"
。
样例输入
3 5
2 1 3
3 2 -6
3 2 1
1 3 2
2 1 8
样例输出
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;
}