国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

POJ 3059 Wormholes

2019-11-11 06:11:12
字體:
來源:轉載
供稿:網友

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; }}
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 东丽区| 博兴县| 勃利县| 阳西县| 三都| 双牌县| 白城市| 河津市| 牙克石市| 闽清县| 望谟县| 宜昌市| 海兴县| 奉贤区| 鹤壁市| 高州市| 喜德县| 台东县| 长武县| 大英县| 张家港市| 黄山市| 大兴区| 全南县| 镇江市| 石阡县| 潍坊市| 承德市| 西乡县| 准格尔旗| 稻城县| 西乌珠穆沁旗| 麻栗坡县| 灌南县| 仁布县| 石棉县| 秀山| 建昌县| 阿合奇县| 富源县| 阳原县|