1038 虫洞 Wormholes 判断负环+各种细节

 链接：https://ac.nowcoder.com/acm/contest/26077/1038
来源：牛客网

题目描述

John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边）连接着N（从1到N标号）块地，并有W个虫洞。
现在John想借助这些虫洞来回到过去（在出发时刻之前回到出发点），请你告诉他能办到吗。John将向你提供F个农场的地图。没有小路会耗费你超过10410^4104秒的时间，当然也没有虫洞回帮你回到超过10410^4104秒以前。

输入描述:

第一行一个整数F，表示农场个数；
对于每个农场：
第一行，三个整数N,M,W；
接下来M行，每行三个数S,E,T，表示在标号为S的地与标号为E的地中间有一条用时T秒的小路；
接下来W行，每行三个数S,E,T，表示在标号为S的地与标号为E的地中间有一条可以使John到达T秒前的虫洞。

输出描述:

输出共F行，如果John能在第i个农场实现他的目标，就在第i行输出YES，否则输出NO。

示例1

输入

复制 2<br />3 3 1<br />1 2 2<br />1 3 4<br />2 3 1<br />3 1 3<br />3 2 1<br />1 2 3<br />2 3 4<br />3 1 8

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

输出

复制 NO<br />YES

NO
YES

备注:

对于全部数据，1≤F≤5,1≤N≤500,1≤M≤2500,1≤W≤200,1≤S,E≤N,∣T∣≤1041 /le F /le 5,1 /le N /le 500,1 /le M /le 2500,1 /le W /le 200,1 /le S,E /le N,|T| /le10^41≤F≤5,1≤N≤500,1≤M≤2500,1≤W≤200,1≤S,E≤N,∣T∣≤104。

分析

1.如果存在负环，则这条负环至少经过n 个点。这样是o（n）

2.如果记录每个点入队次数就要o(n^2)

3.由于可能负环不在根节点位置，所以要预先把所有点放进队列里。

ps：不要忘记初始化

//-------------------------代码----------------------------

//#define int ll
const int N = 1e6+10;
int n,m,w;
V<pii> e[N];
int dist[N];
bool vis[N];
int cnt[N];

bool spfa(int st) {
    ms(dist,0x3f);ms(vis,0);
    queue<int> q;
    fo(i,1,n) {
        dist[i] = 0;
        vis[i] = 1;
        q.push(i);
        cnt[i] = 0;
    }
    while(q.size()) {
        auto t = q.front();q.pop();
        vis[t] = 0;
        for(auto it:e[t]) {
            int ver = it.first,W = it.second;
            if(dist[ver] > dist[t] + W) {
                dist[ver] = dist[t] + W;
                cnt[ver] = cnt[t] + 1;
                if(cnt[ver] >= n) return 1;
                if(!vis[ver])q.push(ver),vis[ver] = 1;
            }
        }
    }
    return 0;
}

void solve()
{
    cin>>n>>m>>w;
    fo(i,1,n) e[i].clear();
    fo(i,1,m) {
        int a,b,c;cin>>a>>b>>c;
        e[a].pb({b,c}),e[b].pb({a,c});
    }
    fo(i,1,w) {
        int a,b,c;cin>>a>>b>>c;
        e[a].pb({b,-c});
    }
    if(spfa(1)) {
        YES;
    } else {
        NO;
    }
}
void main_init() {}
signed main(){
    AC();clapping();TLE;
    cout<<fixed<<setprecision(12);
    main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------