Wormholes虫洞[USACO 2006 Dec]
题目描述
Farmer John 在探索他的农场时发现了许多神奇的虫洞。虫洞的特性非常特殊——它是一个单向通道，能将你传送到它的目的地，而且时间还会回溯到过去！FJ 的每个农场包含 N(1≤N≤500) 块编号为 1∼N 的田地、M(1≤M≤2500) 条双向路径和 W(1≤W≤200) 个虫洞。
作为狂热的时间旅行爱好者，FJ 希望实现：从某块田地出发，经过若干路径和虫洞后，在初始离开时间之前回到起点。这样或许他能遇见自己 :)
为了判断可行性，FJ 将提供 F(1≤F≤5) 个农场的完整地图。所有路径通行耗时不超过 10,000 秒，虫洞最多能将 FJ 带回 10,000 秒前。
输入格式
第 1 行：一个整数 F，表示农场数。后续为 F 个农场的数据。
每个农场：
-
第 1 行：三个空格分隔的整数 N（田地数）, M（双向路径数）, W（虫洞数）。
-
第 2∼M+1 行：每行三个空格分隔的整数 (S,E,T)，表示 S 和 E 间有一条耗时 T 秒的双向路径。两块田地间可能存在多条路径。
-
第 M+2∼M+W+1 行：每行三个空格分隔的整数 (S,E,T)，表示一条从 S 到 E 的单向虫洞，可将 FJ 带回 T 秒前。
输出格式
输出 F 行：对每个农场，若 FJ 能达成目标输出YES，否则输出NO。
输入输出样例
输入 #1复制
2 3 3 1 1 2 2 1 3 4 2 3 1 3 1 3 3 2 1 1 2 3 2 3 4 3 1 8
输出 #1复制
NO YES
说明/提示
-
农场 1：FJ 无法实现时间回溯。
-
农场 2：FJ 可通过环 1→2→3→1 回到起点 1 秒前（可从环上任意点出发实现）。
正解
如果我们把每一条路权值看成通过所用的时间的话，那么我们便可以把虫洞的时间看成负权边，这样的话如果从一个点出发回到这个点所花的时间小于0，则说明虫洞起了作用回到了出发时间之前。相当于判断有没有负环就行了！！！
#include
using namespace std;
int t,g[500001],n,m,d[500001],to[100001],cnt,head[100001],p,Next[100001],w[100001],minn=INT_MAX,Saber[100001];
bool vis[100001];
queueq;
void add(int u,int v,int l)
{
++cnt;
to[cnt]=v;
Next[cnt]=head[u];
head[u]=cnt;
w[cnt]=l;
}
bool spfa()
{
memset(Saber,0,sizeof(Saber));
for(int i=1;i<=n;i++)
d[i]=INT_MAX;
d[1]=0;
q.push(1);
vis[1]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=Next[i])
{
int v=to[i];
if(d[v]>d[u]+w[i])
{
d[v]=d[u]+w[i];
Saber[v]=Saber[u]+1;
if(Saber[v]>n-1)
return 0;
if(!vis[v])
{
q.push(v);
vis[v]=1;
}
}
}
}
return 1;
}
int main()
{
cin>>t;
while(t--)
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
if(z>=0)
add(y,x,z);
}
if(spfa()==0)
cout<<"YES
";
else
cout<<"NO
";
memset(to,0,sizeof(to));
memset(Next,0,sizeof(Next));
memset(head,0,sizeof(head));
memset(w,0,sizeof(w));//清空一下
}
return 0;//完结撒花
}
