poj 3259 Wormholes SPFA // Bellman-ford

本文主要是介绍poj 3259 Wormholes SPFA // Bellman-ford，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//最水的模版题，记下来以后忘了可以看看。

//SPFA

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=505;
int n, m, w, d[maxn], inqueue[maxn], cnt[maxn];
struct node{
int e[maxn], v[maxn], sum;
}edge[maxn];

void add_edge(int s, int e, int v){
    edge[s].e[edge[s].sum]=e;
    edge[s].v[edge[s].sum]=v;
    edge[s].sum++;
}

void init(){
    int i, x, y, c;
    scanf("%d%d%d", &n, &m, &w);
    for(i=1; i<=n; i++){
        edge[i].sum=0;
        cnt[i]=0;
        inqueue[i]=0;
        d[i]=INF;
    }
    for(i=0; i<m; i++){
        scanf("%d%d%d", &x, &y, &c);
        add_edge(x, y, c);
        add_edge(y, x, c);
    }
    for(i=0; i<w; i++){
        scanf("%d%d%d", &x, &y, &c);
        add_edge(x, y, -c);
    }
}

bool spfa(int st){
    int i, head;
    queue<int > q;
    d[st]=0;
    inqueue[st]=1;
    q.push(st);
    cnt[st]=1;
    while(!q.empty()){
        head=q.front();
        q.pop();
        inqueue[head]=0;
        for(i=0; i<edge[head].sum; i++){
            if(d[edge[head].e[i]]>d[head]+edge[head].v[i]){
                d[edge[head].e[i]]=d[head]+edge[head].v[i];
                if(!inqueue[edge[head].e[i]]){
                    inqueue[edge[head].e[i]]=1;
                    cnt[edge[head].e[i]]++;
                    if(cnt[edge[head].e[i]]>=n)
                    return false;
                    q.push(edge[head].e[i]);
                }
            }
        }
    }
    return true;
}
int main(){
    //freopen("1.txt", "r", stdin);
    int T;
scanf("%d", &T);
while(T--){
init();
if(spfa(1))printf("NO\n");
else printf("YES\n");
}
    return 0;
}

//Bellman-ford
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int INF=0xfffffff;
int n, m, w, num, d[505];
struct node{
    int s, e, v;
}edge[5300];void Add_edge(int s, int e, int v){
    edge[num].s=s;
    edge[num].e=e;
    edge[num].v=v;
    num++;
}
void init(){
    int i, x, y, c;
    num=0;
    scanf("%d%d%d", &n, &m, &w);
    for(i=0; i<m; i++){
        scanf("%d%d%d", &x, &y, &c);
        Add_edge(x, y, c);
        Add_edge(y, x, c);
    }
    for(i=0; i<w; i++){
        scanf("%d%d%d", &x, &y, &c);
        Add_edge(x, y, -c);
    }
    for(i=1; i<=n; i++)
    d[i]=INF;
    d[1]=0;
}
bool bellman(){
    int i, j;
    for(i=1; i<n; i++){
        for(j=0; j<num; j++){
            if(d[edge[j].s]+edge[j].v<d[edge[j].e])
                d[edge[j].e]=d[edge[j].s]+edge[j].v;
        }
    }
    for(j=0; j<num; j++){
        if(d[edge[j].s]+edge[j].v<d[edge[j].e])
        return false;
    }
    return true;
}
int main(){
    //freopen("1.txt", "r", stdin);
int i, T;
scanf("%d", &T);
while(T--){
init();
if(bellman())printf("NO\n");
else printf("YES\n");
}
return 0;
}