[USACO06DEC] Wormholes G（spfa判断环）

[USACO06DEC] Wormholes G

题目背景

英文题面见此链接

题目描述

John 在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。

John 的每个农场有 m m m 条小路（无向边）连接着 n n n 块地（从 1 ∼ n 1 \sim n 1∼n 标号），并有 w w w 个虫洞。

现在 John 希望能够从某块地出发，走过一条路径回到出发点，且同时也回到了出发时刻以前的某一时刻。请你告诉他能否做到。

输入格式

输入的第一行是一个整数 T T T，代表测试数据的组数。

每组测试数据的格式如下：

每组数据的第一行是三个用空格隔开的整数，分别代表农田的个数 n n n，小路的条数 m m m，以及虫洞的个数 w w w。

每组数据的第 2 2 2 到第 ( m + 1 ) (m + 1) (m+1) 行，每行有三个用空格隔开的整数 u , v , p u, v, p u,v,p，代表有一条连接 u u u 与 v v v 的小路，经过这条路需要花费 p p p 的时间。

每组数据的第 ( m + 2 ) (m + 2) (m+2) 到第 ( m + w + 1 ) (m + w + 1) (m+w+1) 行，每行三个用空格隔开的整数 u , v , p u, v, p u,v,p，代表点 u u u 存在一个虫洞，经过这个虫洞会到达点 v v v，并回到 p p p 秒之前。

输出格式

对于每组测试数据，输出一行一个字符串，如果能回到出发时刻之前，则输出 YES，否则输出 NO。

样例 #1

样例输入 #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

提示

样例 2 解释

John 只需要沿着 1 → 2 → 3 → 1 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 1→2→3→1 的路径一直转圈即可，每转完一圈，时间就会减少一秒。

数据范围与约定

对于 100 % 100\% 100% 的数据， 1 ≤ T ≤ 5 1 \le T \le 5 1≤T≤5， 1 ≤ n ≤ 500 1 \le n \le 500 1≤n≤500， 1 ≤ m ≤ 2500 1 \le m \le 2500 1≤m≤2500， 1 ≤ w ≤ 200 1 \le w \le 200 1≤w≤200， 1 ≤ p ≤ 1 0 4 1 \le p \le 10^4 1≤p≤104。

思路

这就是很典型的判断是否有环的题目。

代码

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>

using namespace std;

const int N = 2e4+10;

int e[N],ne[N],w[N],h[N],idx;
bool st[N];
int dist[N];
int cnt[N];
int n,m,k;
int T;

void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

bool spfa(){
    queue<int>q;
    memset(dist,0,sizeof dist);
    memset(cnt,0,sizeof cnt);
    memset(st,0,sizeof st);
    
    for(int i=1;i<=n;i++){
        q.push(i);
        st[i]=true;
    }
    
    while(q.size()){
        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 false;
                if(!st[j]){
                    st[j]=true;
                    q.push(j);
                }
            }
        }
    }
    
    return true;
}

int main(){
    // ios::sync_with_stdio(false);
    scanf("%d",&T);
    
    while(T--){
        memset(h,-1,sizeof h);
        idx=0;
        // memset(dist,0x3f,sizeof dist);
        
        // cin>>n>>m>>k;
        scanf("%d%d%d",&n,&m,&k);
        
        for(int i=1;i<=m;i++){
            int a,b,c;
            // cin>>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 u,v,p;
            // cin>>u>>v>>p;
            scanf("%d%d%d",&u,&v,&p);
            add(u,v,-p);
        }
        
        if(!spfa()){
            puts("YES");
        }else{
            puts("NO");
        }
    }
    
    return 0;
}