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 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
F: For each farm, output "YES" if FJ can achieve his goal, otherwise output "NO" (do not include the quotes).
Sample Input
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
Sample Output
NO
YES
Hint
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 ;
}