UVA-558 Wormholes（Floyd）_takes to travel through a wormhole is negligible. -程序员宅基地

技术标签：图论

Description

In the year 2163, wormholes were discovered. A wormhole is a subspace tunnel through space and time connecting two star systems. Wormholes have a few peculiar properties:

Wormholes are one-way only.
The time it takes to travel through a wormhole is negligible.
A wormhole has two end points, each situated in a star system.
A star system may have more than one wormhole end point within its boundaries.
For some unknown reason, starting from our solar system, it is always possible to end up in any star system by following a sequence of wormholes (maybe Earth is the centre of the universe).
Between any pair of star systems, there is at most one wormhole in either direction.
There are no wormholes with both end points in the same star system.

All wormholes have a constant time difference between their end points. For example, a specific wormhole may cause the person travelling through it to end up 15 years in the future. Another wormhole may cause the person to end up 42 years in the past.

A brilliant physicist, living on earth, wants to use wormholes to study the Big Bang. Since warp drive has not been invented yet, it is not possible for her to travel from one star system to another one directly. This can be done using wormholes, of course.

The scientist wants to reach a cycle of wormholes somewhere in the universe that causes her to end up in the past. By travelling along this cycle a lot of times, the scientist is able to go back as far in time as necessary to reach the beginning of the universe and see the Big Bang with her own eyes. Write a program to find out whether such a cycle exists.

Input

The input file starts with a line containing the number of cases c to be analysed. Each case starts with a line with two numbers n and m . These indicate the number of star systems ( $1 \le n \le 1000$ ) and the number of wormholes ( $0 \le m \le 2000$ ) . The star systems are numbered from 0 (our solar system) through n -1 . For each wormhole a line containing three integer numbers x , y and t is given. These numbers indicate that this wormhole allows someone to travel from the star system numbered x to the star system numbered y , thereby ending up t ( $-1000 \le t \le 1000$ ) years in the future.

Output

The output consists of c lines, one line for each case, containing the word possible if it is indeed possible to go back in time indefinitely, or not possible if this is not possible with the given set of star systems and wormholes.

Sample Input

Sample Output

possible
not possible

题目大意:

有很多单向虫洞，经过这个虫洞后穿越到过去或者是未来，一个科学家想要研究宇宙大爆炸（Big Bang）让你判断有没有可能回到过去亲眼目睹宇宙大爆炸。

思路：

既然是要回到过去，肯定需要两个点，从a点到b点，在从b点回到a点之后，穿越到了过去，然后无限循环的走这两个点，总有可能走在宇宙大爆炸前。可以把变化的时间当成是两个点之间的距离。这样就是关键找每两个点之间的距离，然后比较从自身到自身的是否回到了过去。

这里运用到一个方便的算法————Floyd 算法；

思想就是用二维数组存储各个路径，然后判断当每个点都为其他的顶点的中间顶点（比如：从2到3的有一条路，然后从2到1 从1 到3也有条路径判断当1为中间顶点时两条路谁更短一些然后更新即可），中间顶点也可能不唯一，然后判断经过中间节点和不经过中间节点两个路的长度，每次更新到最短。

代码如下：

#include<stdio.h>
#include<string.h>
#include<cmath>
#include<algorithm>
#include<iostream>
#define INF 0x1f1f1f1f
using namespace std;
int s[1010][1010];
int main()
{
    int i, j, k, m, n, t, x, y, time;

    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(s, INF, sizeof(s));
        for(i = 0; i < m; i++)
        {
            scanf("%d%d%d",&x,&y,&time);
            s[x][y] = time;
        }
        for(i = 0; i < n; i++)// 以i为中间顶点
            for(j = 0; j < n; j++)
                if(s[j][i] < INF) // 如果j到i没有路，没有必要判断下面
                    for(k = 0; k < n; k++)
                    {
                        if(s[i][k] < INF)
                        {
                            if(s[i][k] + s[j][i] < s[j][k]) // 判断经过中间顶点路径和不经过的大小
                                s[j][k] = s[i][k] + s[j][i]; //更新路径
                        }
                    }
        int flag = 0;
        for(i = 0; i < n; i++)
        {
            for(j = 0; j < n; j++)
            {
                if(s[i][j] < INF && s[j][i] < INF)
                {
                    if(s[i][j] + s[j][i] < 0)//判断是否有条回路能否走到过去。
                    {
                        flag = 1; // 如果有回路标记
                        break;
                    }
                }
            }
            if(flag)
                break;
        }
        if(flag)
            printf("possible\n");
        else
            printf("not possible\n");
    }
    return 0;
}

本文链接：https://blog.csdn.net/bmamb/article/details/51219875

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

使用nginx解决浏览器跨域问题_nginx不停的xhr-程序员宅基地

文章浏览阅读1k次。通过使用ajax方法跨域请求是浏览器所不允许的，浏览器出于安全考虑是禁止的。警告信息如下：不过jQuery对跨域问题也有解决方案，使用jsonp的方式解决，方法如下：$.ajax({ async:false, url: 'http://www.mysite.com/demo.do', // 跨域URL ty..._nginx不停的xhr

在 Oracle 中配置 extproc 以访问 ST_Geometry-程序员宅基地

文章浏览阅读2k次。关于在 Oracle 中配置 extproc 以访问 ST_Geometry，也就是我们所说的使用空间SQL 的方法，官方文档链接如下。http://desktop.arcgis.com/zh-cn/arcmap/latest/manage-data/gdbs-in-oracle/configure-oracle-extproc.htm其实简单总结一下，主要就分为以下几个步骤。..._extproc

Linux C++ gbk转为utf-8_linux c++ gbk->utf8-程序员宅基地

文章浏览阅读1.5w次。linux下没有上面的两个函数，需要使用函数 mbstowcs和wcstombsmbstowcs将多字节编码转换为宽字节编码wcstombs将宽字节编码转换为多字节编码这两个函数，转换过程中受到系统编码类型的影响，需要通过设置来设定转换前和转换后的编码类型。通过函数setlocale进行系统编码的设置。linux下输入命名locale -a查看系统支持的编码_linux c++ gbk->utf8

IMP-00009: 导出文件异常结束-程序员宅基地

文章浏览阅读750次。今天准备从生产库向测试库进行数据导入，结果在imp导入的时候遇到“ IMP-00009:导出文件异常结束” 错误，google一下，发现可能有如下原因导致imp的数据太大，没有写buffer和commit两个数据库字符集不同从低版本exp的dmp文件，向高版本imp导出的dmp文件出错传输dmp文件时，文件损坏解决办法：imp时指定..._imp-00009导出文件异常结束

python程序员需要深入掌握的技能_Python用数据说明程序员需要掌握的技能-程序员宅基地

文章浏览阅读143次。当下是一个大数据的时代，各个行业都离不开数据的支持。因此，网络爬虫就应运而生。网络爬虫当下最为火热的是Python，Python开发爬虫相对简单，而且功能库相当完善，力压众多开发语言。本次教程我们爬取前程无忧的招聘信息来分析Python程序员需要掌握那些编程技术。首先在谷歌浏览器打开前程无忧的首页，按F12打开浏览器的开发者工具。浏览器开发者工具是用于捕捉网站的请求信息，通过分析请求信息可以了解请..._初级python程序员能力要求

Spring @Service生成bean名称的规则（当类的名字是以两个或以上的大写字母开头的话，bean的名字会与类名保持一致）_@service beanname-程序员宅基地

文章浏览阅读7.6k次，点赞2次，收藏6次。@Service标注的bean，类名：ABDemoService查看源码后发现，原来是经过一个特殊处理：当类的名字是以两个或以上的大写字母开头的话，bean的名字会与类名保持一致public class AnnotationBeanNameGenerator implements BeanNameGenerator { private static final String C..._@service beanname

随便推点

二叉树的各种创建方法_二叉树的建立-程序员宅基地

文章浏览阅读6.9w次，点赞73次，收藏463次。1.前序创建#include<stdio.h>#include<string.h>#include<stdlib.h>#include<malloc.h>#include<iostream>#include<stack>#include<queue>using namespace std;typed_二叉树的建立

解决asp.net导出excel时中文文件名乱码_asp.net utf8 导出中文字符乱码-程序员宅基地

文章浏览阅读7.1k次。在Asp.net上使用Excel导出功能，如果文件名出现中文，便会以乱码视之。解决方法： fileName = HttpUtility.UrlEncode(fileName, System.Text.Encoding.UTF8);_asp.net utf8 导出中文字符乱码

笔记-编译原理-实验一-词法分析器设计_对pl/0作以下修改扩充。增加单词-程序员宅基地

文章浏览阅读2.1k次，点赞4次，收藏23次。第一次实验词法分析实验报告设计思想词法分析的主要任务是根据文法的词汇表以及对应约定的编码进行一定的识别，找出文件中所有的合法的单词，并给出一定的信息作为最后的结果，用于后续语法分析程序的使用；本实验针对 PL/0 语言的文法、词汇表编写一个词法分析程序，对于每个单词根据词汇表输出： (单词种类, 单词的值) 二元对。词汇表：种别编码单词符号助记符0beginb..._对pl/0作以下修改扩充。增加单词

android adb shell 权限,android adb shell权限被拒绝-程序员宅基地

文章浏览阅读773次。我在使用adb.exe时遇到了麻烦.我想使用与bash相同的adb.exe shell提示符,所以我决定更改默认的bash二进制文件(当然二进制文件是交叉编译的,一切都很完美)更改bash二进制文件遵循以下顺序> adb remount> adb push bash / system / bin /> adb shell> cd / system / bin> chm..._adb shell mv 权限

投影仪-相机标定_相机-投影仪标定-程序员宅基地

文章浏览阅读6.8k次，点赞12次，收藏125次。1. 单目相机标定引言相机标定已经研究多年，标定的算法可以分为基于摄影测量的标定和自标定。其中，应用最为广泛的还是张正友标定法。这是一种简单灵活、高鲁棒性、低成本的相机标定算法。仅需要一台相机和一块平面标定板构建相机标定系统，在标定过程中，相机拍摄多个角度下（至少两个角度，推荐10~20个角度）的标定板图像（相机和标定板都可以移动），即可对相机的内外参数进行标定。下面介绍张氏标定法（以下也这么称呼）的原理。原理相机模型和单应矩阵相机标定，就是对相机的内外参数进行计算的过程，从而得到物体到图像的投影_相机-投影仪标定

Wayland架构、渲染、硬件支持-程序员宅基地

文章浏览阅读2.2k次。文章目录Wayland 架构Wayland 渲染Wayland的硬件支持简述：　翻译一篇关于和 wayland 有关的技术文章, 其英文标题为Wayland Architecture .Wayland 架构若是想要更好的理解 Wayland 架构及其与 X (X11 or X Window System) 结构；一种很好的方法是将事件从输入设备就开始跟踪, 查看期间所有的屏幕上出现的变化。这就是我们现在对 X 的理解。内核是从一个输入设备中获取一个事件，并通过 evdev 输入_wayland