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 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 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个虫洞。接着输M行，每行三个数据，分别表示田地编号、田地编号、两田地走路需要的时间。又输入W行，每行三个数据，分别表示田地编号、田地编号、通过虫洞回溯的时间。判断这个人能否在某块田地上出发，经过一系列路和虫洞后，在自己出发之前赶回来。 需要注意，两块田地之间可以有多条路，在赋值时要选择最短的一条赋值。
Floyd-Warshall算法，（特别容易超时）
#include<iostream>#include<vector>#include<algorithm>#include<cstdlib>#include<cmath>#include<stack>#include<queue>#include<cstdio>#include<string>#include<cstring>#include<string.h>#include<map>#include<set>using namespace std;#define N 1000+5#define NN 500000+5#define INF 0x3f3f3f3f/*****************************************************/int d[NN];int cost[N][N];int n, m, mm;struct node{ int u, v; int w;};node s[NN];bool find(){ int j=1; for (int i = 1; i <= n; i++){ for ( j = 1; j <= n; j++){ for (int k = 1; k <= n; k++){ int t = cost[j][i] + cost[i][k]; if (t < cost[j][k]) cost[j][k] = t; } } if (cost[i][i] < 0)return true; } return false;}int main(){ int t; cin >> t; while (t--){ cin >> n >> m >> mm; int edge = 0; memset(cost, 0x3f, sizeof(cost)); for (int i = 0; i < m; i++){ int u, v; int w; scanf("%d%d%d", &u, &v, &w); if (w < cost[u][v]) //在这里选择多条路中的最小路 cost[u][v] = cost[v][u]=w; //无权边 } for (int i = m; i < m + mm; i++){ int u, v; int w; scanf("%d%d%d", &u, &v, &w); cost[u][v] = -w; } if (find()) cout << "YES" << endl; else cout << "NO" << endl; }}新闻热点
疑难解答
