F - 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

23 3 11 2 21 3 42 3 13 1 33 2 11 2 32 3 43 1 8

Sample Output

NOYES

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.

题意：

农夫约翰在探索他的许多农场，发现了一些惊人的虫洞。虫洞是很奇特的，因为它是一个单向通道，可让你进入虫洞的前达到目的地！他的N（1≤N≤500）个农场被编号为1..N，之间有M（1≤M≤2500）条路径，W（1≤W≤200）个虫洞。FJ作为一个狂热的时间旅行的爱好者，他要做到以下几点：开始在一个区域，通过一些路径和虫洞旅行，他要回到最开时出发的那个区域出发前的时间。也许他就能遇到自己了:)。为了帮助FJ找出这是否是可以或不可以，他会为你提供F个农场的完整的映射到（1≤F≤5）。所有的路径所花时间都不大于10000秒，所有的虫洞都不大于万秒的时间回溯。

Input

第1行：一个整数F表示接下来会有F个农场说明。 每个农场第一行：分别是三个空格隔开的整数：N，M和W 第2行到M+1行：三个空格分开的数字（S，E，T）描述，分别为：需要T秒走过S和E之间的双向路径。两个区域可能由一个以上的路径来连接。 第M +2到M+ W+1行：三个空格分开的数字（S，E，T）描述虫洞，描述单向路径，S到E且回溯T秒。

Output

F行，每行代表一个农场 每个农场单独的一行，” YES”表示能满足要求，”NO”表示不能满足要求。

 

思路：

套判断负环的模板即可

先给出我一开始用的spfa算法如下，用时235s：

//// Created by hanyu on 2019/7/19.//#include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int maxn=2e5+7;#define MAX 0x3f3f3f3fint book[maxn],cnt[maxn],d[maxn],head[maxn];int n,m,w;int pos;struct Node{    int s;    int e;    int t;}node[maxn];void add(int s,int e,int t){    node[pos].s=e;    node[pos].e=t;    node[pos].t=head[s];    head[s]=pos++;}bool spfa(int start){    queue
           
            qu;    qu.push(start);    book[start]=1;    d[start]=0;    while(!qu.empty())    {        int now=qu.front();        qu.pop();        book[now]=0;        for(int i=head[now];i!=-1;i=node[i].t)        {            int ss=node[i].s;            int ee=node[i].e;            if(d[ss]>d[now]+ee)            {                d[ss]=d[now]+ee;                if(!book[ss])                {                    qu.push(ss);                    book[ss]=1;                    cnt[ss]++;                    if(cnt[ss]>=n)                    return true;//判断负环                }            }        }    }    return false;}int main(){    int T;    scanf("%d",&T);    while(T--)    {        memset(book,0,sizeof(book));        memset(cnt,0,sizeof(cnt));        memset(d,MAX,sizeof(d));        memset(head,-1,sizeof(head));        memset(node,0,sizeof(node));        scanf("%d%d%d",&n,&m,&w);        int s,e,t;        for(int i=1;i<=m;i++)        {            scanf("%d%d%d",&s,&e,&t);            add(s,e,t);            add(e,s,t);        }        for(int i=1;i<=w;i++)        {            scanf("%d%d%d",&s,&e,&t);            add(s,e,-t);        }        cnt[1]=1;        pos=0;        if(spfa(1))            printf("YES\n");        else            printf("NO\n");    }    return 0;}
           
          
         
        
       

 

然后学习了优化版的Bellmanford算法，发现速度更快，用时79s

//// Created by hanyu on 2019/7/20.//#include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int maxn=6005;#define MAX 0x3f3f3f3fint n,m,w;int pos;int d[maxn];struct Node{    int u,v,w;}node[maxn];void add(int u,int v,int w){    node[++pos].u=u;    node[pos].v=v;    node[pos].w=w;}bool bell(){    memset(d,MAX,sizeof(d));    d[1]=0;    int flag=0;    for(int i=1;i<=n;i++)    {       flag=0;       for(int j=1;j<=pos;j++)       {           if(d[ node[j].v]>d[node[j].u]+node[j].w)           {               d[ node[j].v]=d[node[j].u]+node[j].w;               flag=1;           }       }       if(flag==0)           return false;    }    flag=0;    for(int i=1;i<=pos;i++)    {        if(d[node[i].v]>d[node[i].u]+node[i].w)            return 1;    }    return 0;}int main(){    int T;    int a,b,c;    scanf("%d",&T);    while(T--)    {        pos=0;        scanf("%d%d%d\n",&n,&m,&w);        for(int i=1;i<=m;i++)        {            scanf("%d%d%d",&a,&b,&c);            add(a,b,c);            add(b,a,c);        }        for(int i=1;i<=w;i++)        {            scanf("%d%d%d",&a,&b,&c);            add(a,b,-c);        }        if(bell())            printf("YES\n");        else            printf("NO\n");    }    return 0;}