luogu 2850 [USACO06DEC]虫洞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.

John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边)连接着N （从1..N标号）块地，并有W个虫洞。其中1<=N<=500,1<=M<=2500,1<=W<=200。现在John想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。 John将向你提供F(1<=F<=5)个农场的地图。没有小路会耗费你超过10000秒的时间，当然也没有虫洞回帮你回到超过10000秒以前。

输入格式

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.

输出格式

Lines 1..F: For each farm, output "YES" if FJ can achieve his goal, otherwise output "NO" (do not include the quotes).

输入输出样例

输入 #1

输出 #1

NO
YES

说明/提示

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.

分析

SPFA求负环

SPFA的SLF + swap优化，手工队列

每次队列改变时，比较队首队尾的距离，如果队首大于队尾，则交换队首队尾

代码

  1 /*************************
  2 User：Mandy.H.Y
  3 Language:c++
  4 Problem:luogu 2850
  5 Algorithm:
  6 *************************/
  7 
  8 #include<bits/stdc++.h>
  9 
 10 using namespace std;
 11 
 12 const int maxn = 505;
 13 const int maxm = 2705;
 14 
 15 int t,n,m,ww,size;
 16 int first[maxn],dis[maxn],cnt[maxn];
 17 bool vis[maxn],used[maxn];
 18 int q[1005],l,r;
 19 
 20 struct Edge{
 21     int v,w,nt;
 22 }edge[maxm << 1]; 
 23 
 24 template<class T>inline void read(T &x){
 25     x = 0;bool flag = 0;char ch = getchar();
 26     while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
 27     while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
 28     if(flag) x = -x;
 29 }
 30 
 31 template<class T>void putch(const T x){
 32     if(x > 9) putch(x / 10);
 33     putchar(x % 10 | 48);
 34 }
 35 
 36 template<class T>void put(const T x){
 37     if(x < 9) putchar('-'),putch(-x);
 38     else putch(x);
 39 }
 40 
 41 void file(){
 42     freopen("2850.in","r",stdin);
 43     freopen("2850.out","w",stdout);
 44 }
 45 
 46 void init(){
 47     memset(first,0,sizeof(first));
 48     memset(edge,0,sizeof(edge));
 49     memset(vis,0,sizeof(vis));
 50     memset(used,0,sizeof(used));
 51     memset(cnt,0,sizeof(cnt));
 52     memset(dis,0x3f3f3f3f,sizeof(dis));
 53     size = 0;
 54 }
 55 
 56 void eadd(int u,int v,int w){
 57     edge[ ++ size].v = v;
 58     edge[size].w = w;
 59     edge[size].nt = first[u];
 60     first[u] = size;
 61 }
 62 
 63 void readdata(){
 64     read(n);read(m);read(ww);
 65     for(int i = 1;i <= m; ++ i){
 66         int u,v,w;
 67         read(u);read(v);read(w);
 68         eadd(u,v,w);
 69         eadd(v,u,w);
 70     }
 71     for(int i = 1;i <= ww; ++ i){
 72         int u,v,w;
 73         read(u);read(v);read(w);
 74         eadd(u,v,-w);
 75     }
 76 }
 77 
 78 bool SPFA(int s){
 79     l = r = 0;
 80     q[r ++ ] = s;
 81     while(l != r){
 82         int u = q[l];
 83         l++;
 84         used[u] = 1;
 85         l = l % 1000;
 86         int rr = (r - 1 + 1000) % 1000;
 87         if(l != r) if(dis[q[l]] > dis[q[rr]]) swap(q[l],q[rr]);
 88         vis[u] = 0;
 89         if(cnt[u] > n) return 1;
 90         for(int i = first[u];i;i = edge[i].nt){
 91             int v = edge[i].v;
 92             int w = edge[i].w;
 93             if(dis[u] + w < dis [v]){
 94                 dis[v] = dis[u] + w;
 95                 cnt[v] = cnt[u] + 1;
 96                 if(!vis[v]){
 97                     q[r++] = v;
 98                     vis[v] = 1;
 99                     r %= 1000;
100                     int rr = (r - 1 + 1000) % 1000;
101                     if(l != r) if(dis[q[l]] > dis[q[rr]]) swap(q[l],q[rr]);
102                 }
103             }
104         }
105     }
106     return 0;
107 }
108 
109 void work(){
110     init();
111     readdata();
112     
113     for(int i = 1; i <= n; ++ i){
114         if(!used[i]) {
115             if(SPFA(i)) {
116                 puts("YES");
117                 return;
118             }
119         }
120     }
121     puts("NO");
122 }
123 
124 int main(){
125 //    file();
126     read(t);
127     while(t -- ) work();
128     return 0;
129 }

View Code