Wormholes
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.
Source
题目类型：单源最短路(SPFA)判负圈
算法分析：按照题目的要求建好邻接表，然后使用SPFA算法计算并统计每一个点入队列的次数，如果有点的入队次数大于n-1次，则可直接判断图中存在负权值回路
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
#include <iostream> #include <fstream> #include <algorithm> #include <iomanip> #include <cstring> #include <cstdio> #include <cmath> #include <map> #include <string> #include <vector> #include <stack> #include <queue> #include <set> #include <list> #include <ctime> using namespace std; const int maxn = 666 + 66; const int INF = 66666666; struct Node { int v, w; Node (int vv, int ww) : v (vv), w (ww) {} Node () {} }; bool inq[maxn]; int dis[maxn], cnt[maxn]; int n, m, w; vector <Node> edge[maxn]; bool spfa () { int i; memset (inq, false, sizeof (inq)); memset (cnt, 0, sizeof (cnt)); for (i = 0; i < maxn; i++) dis[i] = INF; dis[1] = 0; inq[1] = true; queue <int> q; q.push (1); cnt[1]++; while (!q.empty ()) { int temp = q.front (); q.pop (); inq[temp] = false; if (cnt[temp] >= n) return true; int i; for (i = 0; i < edge[temp].size (); i++) { if (dis[edge[temp][i].v] > dis[temp] + edge[temp][i].w) { dis[edge[temp][i].v] = dis[temp] + edge[temp][i].w; if (!inq[edge[temp][i].v]) { q.push (edge[temp][i].v); inq[edge[temp][i].v] = true; cnt[edge[temp][i].v]++; } } } } return false; } int main() { // ifstream cin ("aaa.txt"); int t; cin >> t; while (t--) { cin >> n >> m >> w; int i; for (i = 0; i < maxn; i++) edge[i].clear (); int val_u, val_v, val_w; for (i = 0; i < m; i++) { cin >> val_u >> val_v >> val_w; edge[val_u].push_back (Node (val_v, val_w)); edge[val_v].push_back (Node (val_u, val_w)); } for (i = 0; i < w; i++) { cin >> val_u >> val_v >> val_w; edge[val_u].push_back (Node (val_v, -val_w)); } if (spfa ()) cout << "YES" << endl; else cout << "NO" << endl; } return 0; } |
- « 上一篇：poj3250
- poj3264：下一篇 »