class {} res ont nal farmer orm sizeof size
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.
Sample Output
- 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
Hint
- NO
- YES
- const int inf = 1 << 29;
- int n,
- m,
- w;
- struct ed {
- int to,
- cost;
- ed(int _t = 0, int _c = 0) : to(_t),
- cost(_c) {}
- };
- vector < ed > edge[505];
- bool vis[505];
- int d[505];
- int cnt[505];
- bool spfa() {
- queue < int > que;
- memset(cnt, 0, sizeof(cnt));
- memset(vis, false, sizeof(vis));
- for (int i = 1; i <= 500; i++) d[i] = inf;
- d[1] = 0;
- cnt[1] = 1;
- que.push(1);
- while (!que.empty()) {
- int u = que.front();
- que.pop();
- vis[u] = false;
- for (int i = 0; i < edge[u].size(); i++) {
- int to = edge[u][i].to;
- int cost = edge[u][i].cost;
- if (d[u] + cost < d[to]) {
- d[to] = d[u] + cost;
- if (!vis[to]) {
- vis[to] = true;
- que.push(to);
- cnt[to]++;
- if (cnt[to] > n) return true;
- }
- }
- }
- }
- return false;
- }
- int main() {
- int t;
- int a,
- b,
- c;
- cin >> t;
- while (t--) {
- scanf("%d%d%d", &n, &m, &w);
- for (int i = 1; i <= 500; i++) edge[i].clear();
- for (int i = 1; i <= m; i++) {
- scanf("%d%d%d", &a, &b, &c);
- edge[a].push_back(ed(b, c));
- edge[b].push_back(ed(a, c));
- }
- for (int i = 1; i <= w; i++) {
- scanf("%d%d%d", &a, &b, &c);
- edge[a].push_back(ed(b, -c));
- }
- if (spfa()) printf("YES\n");
- else printf("NO\n");
- }
- return 0;
- }
最短路 - spfa
来源: http://www.bubuko.com/infodetail-2381186.html