Wormholes

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Description

While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ's farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1.. N , M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.

As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .

To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.

Input

Line 1: A single integer, F . F farm descriptions follow.
Line 1 of each farm: Three space-separated integers respectively:
N ,
M , and W
Lines 2..
M +1 of each farm: Three space-separated numbers (
S ,
E ,
T ) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path.

Lines M +2..
M +
W +1 of each farm: Three space-separated numbers (
S ,
E ,
T ) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.

Output

Lines 1..
F : For each farm, output "YES" if FJ can achieve his goal, otherwise output "NO" (do not include the quotes).

Sample Input

Sample Output

NO

YES

Hint

For farm 1, FJ cannot travel back in time.
For farm 2, FJ could travel back in time by the cycle
1->2->3->1, arriving back at his starting location 1 second
before he leaves. He could start from anywhere on the cycle to
accomplish this.

题目大意就是：农夫约翰有F个农场，每个农场有N块地，其间有M条路（无向），W条时光隧道（有向且时间倒流即：权值为负）。问是否可能回到过去？

经典的bellman_Ford理解题，不知道的可以去百度！

//Asimple

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <vector>

#include <cctype>

#include <cstdlib>

#include <stack>

#include <cmath>

#include <set>

#include <map>

#include <string>

#include <queue>

#include <limits.h>

#include <time.h>

#define INF 0x3f3f3f3f

using namespace std;

const int maxn = ;

typedef long long ll;

int n, m, num, T, k, x, y, len;

int Map[maxn][maxn];

int dis[maxn];

typedef struct node {

    int begin;

    int end;

    int weight;

    node(){}

    node(int begin, int end, int weight) {

        this->begin = begin;

        this->end = end;

        this->weight = weight;

    }

}eee;

eee edg[maxn];

//Bellman-Ford算法：求含负权图的单源最短路径算法

//单源最短路径(从源点s到其它所有顶点v)

bool bellmanFord() {

    memset(dis, , sizeof(dis));

    for(int i=; i<n; i++) {

        for(int j=; j<len; j++) {

            eee e = node(edg[j].begin, edg[j].end, edg[j].weight);

            if( dis[e.end] > dis[e.begin] + e.weight) {

                dis[e.end] = dis[e.begin] + e.weight;

                if( i == n- ) return true;

            }

        }

    }

    return false;

}

void input() {

    cin >> T ;

    while( T -- )  {

        cin >> n >> m >> k;

        len = ;

        for(int i=; i<m; i++) {

            cin >> x >> y >> num;

            edg[len].begin = x;

            edg[len].end = y;

            edg[len].weight = num;

            len ++;

            edg[len].begin = y;

            edg[len].end = x;

            edg[len].weight = num;

            len ++;

        }

        for(int i=; i<k; i++) {

            cin >> x >> y >> num ;

            edg[len].begin = x;

            edg[len].end = y;

            edg[len].weight = -num;

            len ++;

        }

        if( bellmanFord() ) cout << "YES" << endl;

        else cout << "NO" << endl;

    }

}

int main(){

    input();

    return ;

}

2017-5-26　　修改：

自己写了一个邻接矩阵的SPFA解法

坑点：可能会出现重复的路径，这个时候需要取小值。

#include <iostream>

#include <cstring>

#include <queue>

using namespace std;

const int maxn = +;

const int INF = ( <<  );

int n, m, x, y, num, T, k;

int Map[maxn][maxn], dis[maxn], c[maxn];

void init(){

    for(int i=; i<=n; i++) {

        dis[i] = INF;

        c[i] = ;

        for(int j=; j<=n; j++) {

            Map[i][j] = INF;

        }

    }

}

bool spfa(){

    bool vis[maxn];

    queue<int> q;

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

    q.push();

    vis[] = true;

    c[] = ;

    dis[] = ;

    while( !q.empty() ) {

        x = q.front();q.pop();

        vis[x] = false;

        for(int i=; i<=n; i++) {

            if( dis[i]>dis[x]+Map[x][i] ) {

                dis[i] = dis[x]+Map[x][i];

                if( !vis[i] ) {

                    vis[i] = true;

                    c[i] ++;

                    if( c[i]>=n ) return true;

                    q.push(i);

                }

            }

        }

    }

    return false;

}

int main(){

    cin >> T;

    while( T -- ) {

        cin >> n >> m >> k;

        init();

        while( m -- ) {

            cin >> x >> y >> num;

            Map[x][y] = min(Map[x][y], num);

            Map[y][x] = Map[x][y];

        }

        while( k -- ) {

            cin >> x >> y >> num;

            Map[x][y] = min(Map[x][y], -num);

        }

        if( spfa() ) cout << "YES" << endl;

        else cout << "NO" << endl;

    }

    return ;

}