题面

点击此处前往原题。

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

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

现在 John 想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。

题解

SPFA判断负环板子。

代码

#include <bits/stdc++.h>
#define MANX 505
using namespace std;
struct node {
    int dis, nex;
} f;
vector< node > mp[MANX];
int sum[MANX], fl[MANX] = { 0 }, flag;
void spfa( int k ) {
    if ( fl[k] == 1 ) {
        fl[k] = 0;
        flag = 1;
        return;
    }
    fl[k] = 1;
    if ( !mp[k].empty() )
        for ( int i = 0; i < mp[k].size(); i++ ) {
            if ( sum[mp[k][i].nex] > mp[k][i].dis + sum[k] ) {
                sum[mp[k][i].nex] = mp[k][i].dis + sum[k];
                spfa( mp[k][i].nex );
                if ( flag == 1 ) {
                    fl[k] = 0;
                    return;
                }
            }
        }
    fl[k] = 0;
}
int main() {
    ios::sync_with_stdio( false );
    cin.tie( 0 );
    int test, m, n = 0, w, x, y, z, k;
    cin >> test;
    while ( test-- ) {
        for(unsigned int i=1;i<=n;i++){
            mp[i].clear();
        } 
        cin >> n >> m >> k;
        for ( int i = 1; i <= m; i++ ) {  
            cin >> x >> y >> z;
            f.dis = z;
            f.nex = y;
            mp[x].push_back( f );
            f.nex = x;
            mp[y].push_back( f );
        }
        for ( int i = 1; i <= k; i++ ) {
            cin >> x >> y >> z;
            f.dis = -z;
            f.nex = y;
            mp[x].push_back( f );
        }
        memset( sum, 0, sizeof( sum ) );
        flag = 0;
        for ( int i = 1; i <= n; i++ ) {
            spfa( i );
            if ( flag ) {
                break;
            }
        }
        if ( flag == 1 ) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

版权声明：本文是原创文章，版权归 星雾月雨 所有。

本文链接：https://www.ariels.xyz/archives/805.html

本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。