POJ - 3259 Wormholes（Flody，SPFA）

POJ - 3259 Wormholes（Flody，SPFA）

如果Farmer John从1号店出发，经过农场的时间，小于虫洞出发返回的时间，则他可以见到自己，紧接着可以判断图中是否存在负环。

Flody算法和SPFA算法都可以实现

SPFA

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N = 510, M = 5100;
int h[N], e[M], w[M], ne[M], idx;
int dist[N],cnt[N];
bool st[N];
int n,m,k;
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
bool spfa(int s)
{
    memset(dist,0,sizeof dist);memset(cnt,0,sizeof cnt);memset(st,false,sizeof st);queue<int> q;for(int i=1;i<=n;i++){
    q.push(i);st[i]=true;}while(!q.empty()){
    int t=q.front();q.pop();st[t]=false;for(int i=h[t];~i;i=ne[i]){
    int j=e[i];if(dist[j]>dist[t]+w[i]){
    dist[j]=dist[t]+w[i];cnt[j]=cnt[t]+1;if(cnt[j]>=n) return true;if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入{
    q.push(j);st[j]=true;}}}}return false;
}
int main()
{
    int T;scanf("%d",&T);while(T--){
    memset(h,-1,sizeof h);idx=0;scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++){
    int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c),add(b,a,c);}for(int i=1;i<=k;i++){
    int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,-c);}if(spfa(1)) puts("YES");else puts("NO"); }return 0;
}

Flody

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 510, INF = 1e9; 
int dp[N][N],n,m,w;
int floyd()
{
    for(int k=1;k<=n;k++)for(int i=1;i<=n;i++){
    if(dp[i][k]!=INF)for(int j=1;j<=n;j++)if(dp[i][j]>dp[i][k]+dp[k][j])dp[i][j]=dp[i][k]+dp[k][j];if(dp[i][i]<0) return 1;}return 0;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin>>T;while(T--){
    cin>>n>>m>>w;for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)if(i==j) dp[i][j]=0;else dp[i][j]=INF;int s,e,t;while(m--){
    cin>>s>>e>>t;if(dp[s][e]>t) dp[s][e]=dp[e][s]=t;}while(w--){
    cin>>s>>e>>t;if(dp[s][e]>-t) dp[s][e]=-t;}if(floyd()) puts("YES");else puts("NO");}return 0;
}