poj 3259 Wormholes-白红宇

poj 3259 Wormholes

阅读量：6707 次

发布时间：2019-06-25

本文共 3245 字，大约阅读时间需要 10 分钟。

Wormholes

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 52062		Accepted: 19373

Description

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 farm descriptions follow.

Line 1 of each farm: Three space-separated integers respectively:

M, and

Lines 2..

M+1 of each farm: Three space-separated numbers (

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 (

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.

Source

/** @Author: Lyucheng* @Date:   2017-07-22 10:08:50* @Last Modified by:   Lyucheng* @Last Modified time: 2017-07-22 11:28:48*//* 题意：给你一个图，无向边，其中有一条负边，问你有没有可能从一点出发，然后回到一点（看到原来的自己） 思路：建图判断一下是不是有负环*/#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #define MAXN 505#define MAXM 3005#define INF 0x3f3f3f3fusing namespace std;struct Edge { int from,to,dist; Edge(int f,int t,int d):from(f),to(t),dist(d){} }; struct BellmanFord { int n,m; //点数和边数,编号都从0开始 vector
                  
                    edges; //边列表 vector
                   
                     G[MAXN];//每个节点出发的边编号(从0开始编号) bool inq[MAXN]; //是否在队列中 int d[MAXN]; //s到各个点的距离 int p[MAXN]; //最短路中的上一条弧 int cnt[MAXN]; //进队次数 void init(int n) { this->n=n; for(int i=0;i

Q; memset(inq,0,sizeof(inq)); memset(cnt,0,sizeof(cnt)); for(int i=0;i

d[u]+e.dist) { d[e.to] = d[u]+e.dist; p[e.to] = G[u][i]; if(!inq[e.to]) { Q.push(e.to); inq[e.to]=true; if(++cnt[e.to]>n) return true; } } } } return false; } }BF; int t;int n,m,w;int x,y,z;int main(){ // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d",&t); while(t--){ scanf("%d%d%d",&n,&m,&w); BF.init(n); for(int i=0;i

转载于:https://www.cnblogs.com/wuwangchuxin0924/p/7220766.html

你可能感兴趣的文章