I - Wormholes

2024-04-11 15:48
文章标签 wormholes

本文主要是介绍I - 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..NM (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, FF farm descriptions follow. 
Line 1 of each farm: Three space-separated integers respectively: NM, and W 
Lines 2.. M+1 of each farm: Three space-separated numbers ( SET) 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.. MW+1 of each farm: Three space-separated numbers ( SET) that describe, respectively: A one way path from S to E that also moves the traveler backT 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

题意:

昆虫洞

给你一个F,代表有F组测试数据。

第1行,3个数,N,M,W。

第2行到M+1行,每行3个数S,E,T,表示一条从S到E的双向路,通过这条路需要时间T,两块地之间至多有一条路。

第M+2到M+W+1行,每行3个数S,E,T,表示一条从S到E的单向路,通过这条路需要时间-T,即时间倒退T;

求从某块地出发,通过一些路和昆虫洞后还回原点,时间比他出发的时间早,使他能碰到出发前的他自己。

思路:

从题目就可以知道,这是一道最短路问题,而且还有负权边,所以应该用Bellman—Ford算法,同时还要判断是否存在负权边,判断方法在代码中讲。

代码如下:

#include<stdio.h>
#include<string.h>
#define inf 999999999int t,n,m,k,s;
int a,b,c,flag;
int v[6001],u[6001],w[6001];
int dis[6001];void init()//初始化;
{for(int i=2; i<=n; i++)dis[i]=inf;return ;
}void panduan()//判断是否存在负权边;
{for(int i=1; i<=s; i++){if(dis[v[i]]>dis[u[i]]+w[i])flag=1;}return ;
}void Bellman_ford()
{int i,j;init();dis[1]=0;flag=0;for(i=1; i<=n; i++){for(j=1; j<=s; j++){if(dis[v[j]]>dis[u[j]]+w[j])dis[v[j]]=dis[u[j]]+w[j];}}panduan();//如果进行了N-1次的放缩后还能够放缩,那么就存在负权边;if(flag==1)printf("YES\n");elseprintf("NO\n");return ;
}int main()
{scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&k);int i,j;s=1;for(i=1; i<=m;i++)//注意是双向路;{scanf("%d%d%d",&a,&b,&c);u[s]=a;v[s]=b;w[s++]=c;v[s]=a;u[s]=b;w[s++]=c;}for(i=1; i<=k; i++)//注意是单向路;{scanf("%d%d%d",&a,&b,&c);u[s]=a;v[s]=b;w[s++]=-c;}Bellman_ford();}return 0;
}

 

这篇关于I - Wormholes的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/894514

相关文章

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 3259 Wormholes 最短路

题目大意:虫洞问题,现在有n个点,m条边,代表现在可以走的通路,比如从a到b和从b到a需要花费c时间,现在在地上出现了w个虫洞,虫洞的意义就是你从a到b话费的时间是-c(时间倒流,并且虫洞是单向的),现在问你从某个点开始走,能回到从前 解题思路:其实给出了坐标,这个时候就可以构成一张图,然后将回到从前理解为是否会出现负权环,用bellman-ford就可以解出了

UVA558 - Wormholes(BellmanFord判负环)

UVA558 - Wormholes(BellmanFord判负环) UVA558 - Wormholes 题目大意:  有一个教授希望利用虫洞回到过去(还是从这个虫洞出来就到达了过去),给你虫洞形成的有向图,问教授能否回到过去。 解题思路:  利用BellmanFord判负环,如果不存在负环的话,那么最多经过N - 1次迭代就可以得到最短路,因为形成最短路最多N - 1个节点(起点不算

UVa12227/LA4618 Wormholes

UVa12227/LA4618 Wormholes 题目链接题意分析测试数据AC 代码 题目链接   本题是2009年icpc欧洲区域赛西北欧赛区的j题   UVA - 12227 Wormholes 题意   你有一艘星际飞船,飞船运行速度为1,打算从坐标a旅行到坐标b(出发时刻为0),已知n个虫洞(0≤n≤ 50)的信息:入口点坐标s,出口点坐标e,形成时间t,穿过虫洞

POJ3259 Wormholes 【Bellmanford判断是否存在负回路】

很简单的bellmanford题目,这里比较详细:http://blog.csdn.net/lyy289065406/article/details/6645790 直接代码 #include <cstdio>#include <cstdlib>#include <iostream>#include <algorithm>#include <cstring>#include <cma

POJ - 3259 Wormholes(判断负环, Bellman Ford,SPFA)

虫洞能够时光倒流,判断能否在回到出发的位置的时候在出发的时候之前。(判断是否存在负环) 初学最短路,尝试着用了三种方法判断: 1、Bellman Ford (令d全部为0,仅用来判断负环)       OJ测试得157MS 2、Bellman Ford 结束后再来一轮松弛若松弛成功则存在负环。    235MS 3、Bellman Ford 用队列优化过的SPFA,判断是否存在一个点同队大

Wormholes POJ3259 (spfa)

题目:http://poj.org/problem?id=3259 题目大意:F组数据, 输入n, m, w,表示n块田地, m个田与田之间的关系,w个虫洞,从一块田到达另一块田需要花一定时间, 穿过虫洞时时间会倒流,问是否能够回到出发前的时间 解题思路:判断是否存在负环,若存在则一定能够回去。 #include<cstdio>#include<cstring>#include<algo

POJ 3259 *** Wormholes

题意:农场主有f个农场,每个农场有n个田地,m条路,w个虫洞,走路从田地s到田地e需要花费t1时间,而每个虫洞可以从田地q到田地p,且使得时间倒流t2。求对于每个农场,农场主是否能从田地i出发,回到田地i的时间是在他出发的时间之前? 想法:其实就是判断田地之间是否存在负循环,用bellmanford算法就可以了,但是还是WA了两次。因为我忽略了这m条路事实上是可以往返的。

poj 3259 Wormholes SPFA // Bellman-ford

//最水的模版题,记下来以后忘了可以看看。 //SPFA #include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int INF=0x3f3f3f3f; const int maxn=505; int n, m, w, d[maxn], inqueue[ma

【POJ No. 3259】虫洞 Wormholes

【POJ No. 3259】虫洞 Wormholes POJ题目地址 【题意】 在探索许多农场时,约翰发现了一些令人惊奇的虫洞。虫洞是非常奇特的,因为它是一条单向路径,可以将人穿越到虫洞之前的某个时间!约翰想从某个地点开始,穿过一些路径和虫洞,并在他出发前的一段时间返回起点,也许他将能够见到自己。 【输入输出】 输入: 第1行是单个整数F (1≤F ≤5),表示农场的数量。 每个