时光机
蒜头君生活的宇宙有 nn 个星球，有 mm 条虫洞。蒜头君发明了时光机，利用虫洞进行时光旅行。这 mm 条虫洞，第 ii 条虫洞能实现星球 a_iai到 b_ibi 的单向旅行。蒜头君发明的时光机不稳定，通过第 ii 条虫洞能够使得时间前进或者倒退 c_ici（c_i \ge 0ci≥0 表示前进，c_i < 0ci<0 表示倒退）。
如果通过时光机能够让时间无限倒退，那么将会掉进时间漩涡，从而实现穿越。那么蒜头君发明的时光机能否实现穿越（蒜头君可以从任何星球开始）。
输入格式
输入第一行两个整数 n(1 \le n \le 1000)n(1≤n≤1000)，m( 1\le m \le 10000)m(1≤m≤10000)。
接下来 mm 行，第 ii 每行输入 33 个整数 a_i, b_i(1 \le a_i, b_i \le n)ai,bi(1≤ai,bi≤n)，c_i(-10000 \le c_i \le 10000)ci(−10000≤ci≤10000)，表示一个虫洞。
输出格式
如果蒜头军能实现穿越，输出"Yes"，否则输出"No"。、
#include <iOStream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e3 + 9;
const int M = 1e4 + 9;
const int inf = 0x3f3f3f3f3f;
struct edge {
int v, w, fail;
edge() {}
edge(int _v, int _w, int _fail) {
v = _v;
w = _w;
fail = _fail;
}
};
edge e[M << 1];
int head[N], len;
void init() {
memset(head, -1, sizeof head);
len = 0;
}
void add(int u, int v, int w) {
e[len] = edge(v, w, head[u]);
head[u] = len++;
}
void add2(int u, int v, int w) {
add(u, v, w);
add(v, u, w);
}
int n, m;
int dis[N],in[N];
bool vis[N];
bool SPFA(int u){
memset(vis,false,sizeof vis);
vis[u]=true;
memset(dis,inf,sizeof dis);
dis[u]=0;
memset(in,0,sizeof in);
in[u]=1;
queue<int> q;
q.push(u);
u=q.front();
q.pop();
vis[u]=false;
for(int j=head[u];~j;j=e[j].fail){
int v=e[j].v;
int w=e[j].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
if(!vis[v]){
q.push(v);
vis[v]=true;
in[v]++;
if(in[v]>n){
return true;
}
}
}
}
}
}
int main() {
init();
int u, v, w;
cin >> n >> m;
while (m--) {
cin >> u >> v >> w;
add(u, v, w);
}
for(int i=1;i<=n;i++){
add(0,i,0);
}
if(SPFA(1)){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
return 0;
}
相关阅读
宝贝时光机是一款以视频拍摄为主，全家参与记录宝宝成长的工具，同时可以和亲友分享宝宝故事，在社区交流拍摄经验。一、文档说明“宝贝
近日，“淘宝十周年时光机”正式发布，这款小小的“时光机”可以让你看到自己从2003年淘宝成立之后到2013年的支付宝消费状况。我们看
前言背景介绍随着互联网的日益普及QQ已成为几乎每个用户的必备软件，其忠诚度甚至高于手机号，腾讯在今年“六·一”儿童节之际推出了