POJ 3259 Wormholes（最短路&spfa正权回路）题解

题意：给你m条路花费时间（双向正权路径），w个虫洞返回时间（单向负权路径），问你他能不能走一圈回到原点之后，时间倒流。

思路：题意有点难看懂，我们建完边之后找一下是否存在负权回路，存在则能，反之不能。判断负权回路可以用一个cnt，这个spfa板子里有。

代码：

#include<cstdio>

#include<set>

#include<vector>

#include<cmath>

#include<queue>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn = 500+5;

const int INF = 0x3f3f3f3f;

struct Edge{

    int v;

    int w;

    Edge(int _v = 0,int _w = 0):v(_v),w(_w){}

};

vector<Edge> G[maxn];

bool vis[maxn];

int cnt[maxn];

int dis[maxn];

bool spfa(int start,int n){

    memset(vis,false,sizeof(vis));

    for(int i = 1;i <= n;i++) dis[i] = INF;

    vis[start] = true;

    dis[start] = 0;

    queue<int> q;

    while(!q.empty()) q.pop();

    q.push(start);

    memset(cnt,0,sizeof(cnt));

    cnt[start] = 1;

    while(!q.empty()){

        int u = q.front();

        q.pop();

        vis[u] = false;

        for(int i = 0;i < G[u].size();i++){

            int v = G[u][i].v;

            int w = G[u][i].w;

            if(dis[v] > dis[u] + w){

                dis[v] = dis[u] + w;

                if(!vis[v]){

                    q.push(v);

                    vis[v] = true;

                    if(++cnt[v] > n)

                        return true;

                }

            }

        }

    }

    return false;

}

void addEdge(int u,int v,int w){

    G[u].push_back(Edge(v,w));

}

int main(){

    int n,m,w;

    int T;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d%d",&n,&m,&w);

        for(int i = 1;i <= n;i++) G[i].clear();

        int s,e,t;

        while(m--){

            scanf("%d%d%d",&s,&e,&t);

            addEdge(s,e,t);

            addEdge(e,s,t);

        }

        while(w--){

            scanf("%d%d%d",&s,&e,&t);

            addEdge(s,e,-t);

        }

        if(spfa(1,n)){

            printf("YES\n");

        }

        else{

            printf("NO\n");

        }

    }

    return 0;

}