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; }}新聞熱點
疑難解答
