POJ3259
题意：
问是否能通过虫洞回到过去；虫洞是一条单向路，不但会把你传送到目的地，而且时间会倒退Ts。我们把虫洞看成是一条负权路，问题就转化成求一个图中是否存在负权回路；
利用spfa求有无负环的bfs方法：判断是否存在一个点入队次数大于总顶点数。**
Bellman:
#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
using namespace std;
typedef long long ll;
#define maxn 5100
struct edge{ll s,e,w; //起点终点权值
}e[maxn];
ll f,n,m,w,cnt=0,d[maxn],u,v,cost;
bool Bellman(){for(int i=0;i<=n;i++) d[i]=inf;d[0]=0;for(int i=0;i<n;i++){for(int j=0;j<cnt;j++){if(d[e[j].e]>d[e[j].s]+e[j].w){d[e[j].e]=d[e[j].s]+e[j].w;}}}//还能更新存在负环for(int i=0;i<cnt;i++){if(d[e[i].e]>d[e[i].s]+e[i].w){return 1; //存在负环 }} return 0;
}
int main(){cin>>f;while(f--){cin>>n>>m>>w;cnt=0;for(int i=0;i<m;i++){ //双向路径 cin>>u>>v>>cost;e[cnt].s=u;e[cnt].e=v;e[cnt].w=cost;cnt++;e[cnt].s=v;e[cnt].e=u;e[cnt].w=cost;cnt++;// sf("%lld%lld%lld",&e[cnt].s,&e[cnt].e,e[cnt++].w);}for(int i=0;i<w;i++){cin>>u>>v>>cost;e[cnt].s=u;e[cnt].e=v;e[cnt].w=-cost;cnt++;}if(Bellman()){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}return 0;
}spfa判断是否存在负环：
/*首先理解清楚spfa算法的实现原理，起初是源结点入队， 当队列非空时，将以源结点为起点的所有边（用到邻接表） 的终点进行松弛，一旦这些边变小了，就将对应的结点入队， 重复操作直到队列为空。如果一个点的入队次数大于n-1, 就说明存在负环*/#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<queue>
#define maxn 110
#define inf 0x3f3f3f
using namespace std;
int n,m,w;
int dis[maxn],cnt[maxn];
bool vis[maxn];struct node{int end,val;
};
vector<node> v[maxn]; //邻接表bool spfa(){memset(vis,false,sizeof(vis));memset(dis,inf,sizeof(dis));memset(cnt,0,sizeof(cnt));dis[1]=0,vis[1]=true,cnt[1]=1;queue<int> q;q.push(1); //源点入队while(!q.empty()){int x=q.front();q.pop();vis[x]=false;int len=v[x].size (); //遍历以头结点x为起始点的所有边的终点for(int i=0;i<len;i++){int ed=v[x][i].end ;int va=v[x][i].val ;//如果实现了松弛并且该点不在队列中，则入队if(dis[ed]>dis[x]+va){dis[ed]=dis[x]+va;if(!vis[ed]){vis[ed]=true;cnt[ed]++;//如果一个结点入队的次数多于n，则存在负环if(cnt[ed]>=n) return true;q.push (ed);}}}}return false;
}int main(){int cases,s,e,t;cin>>cases;while(cases--){int i;node a;cin>>n>>m>>w; //n个点，m个双向边，w个单向负边for(i=0;i<n;i++)v[i].clear ();for(i=0;i<m;i++){ //双向边cin>>s>>e>>t;a.end=e,a.val=t;v[s].push_back (a);a.end =s, a.val =t;v[e].push_back (a);}for( i=0;i<w;i++){ //单向的cin>>s>>e>>t;a.end =e,a.val =-t;v[s].push_back (a);}if(spfa())cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}floyed判断负环T了。。。。。。。。。。。。。。。。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
using namespace std;
typedef long long ll;
#define maxn 510
ll f,n,m,w,s,e,t,mp[maxn][maxn];int floyed(){for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(mp[i][j]>mp[i][k]+mp[k][j]){mp[i][j]=mp[i][k]+mp[k][j];}if(mp[i][i]<0) return 0;}}}return 1;
}int main(){scanf("%lld",&f);while(f--){scanf("%lld%lld%lld",&n,&m,&w);fill(mp[0],mp[0]+maxn*maxn,inf);for(int i=1;i<=n;i++) mp[i][i]=0;for(int i=0;i<m;i++){//scanfscanf("%lld%lld%lld",&s,&e,&t);if(t<mp[s][e]){mp[s][e]=mp[e][s]=t; //双向 }}for(int i=0;i<w;i++){scanf("%lld%lld%lld",&s,&e,&t);t=-t;if(t<mp[s][e]){mp[s][e]=t; //单向 }}//solveint ans=floyed();if(ans) printf("NO\n");else printf("YES\n");}return 0;
}