904. 虫洞_虫洞引擎

904. 虫洞_虫洞引擎Acwing904.虫洞

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

Powered by:NEFU AB-IN

Link

904. 虫洞

  • 题意

    见原题

  • 思路

    看是否有负环即可

    • 别忘把所有点都入队
  • 代码

    ''' Author: NEFU AB-IN Date: 2022-04-16 16:17:22 FilePath: \ACM\Acwing\904.py LastEditTime: 2022-04-16 16:17:23 '''
    from collections import deque
    N = 550
    INF = int(1e9)
    g = [[] for _ in range(N)]
    dist, st, cnt = [INF] * N, [0] * N, [0] * N
    def spfa():
    q = deque()
    for i in range(1, n + 1):
    q.appendleft(i)
    st[i] = 1
    dist[i] = 0
    while q:
    u = q.pop()
    st[u] = 0
    for v, w in g[u]:
    if dist[v] > dist[u] + w:
    dist[v] = dist[u] + w
    if st[v] == 0:
    st[v] = 1
    q.appendleft(v)
    cnt[v] = cnt[u] + 1
    if cnt[v] >= n:
    return 1
    return 0
    for _ in range(int(input())):
    g = [[] for _ in range(N)]
    dist, st, cnt = [INF] * N, [0] * N, [0] * N
    n, m, w = map(int, input().split())
    for i in range(m):
    u, v, t = map(int, input().split())
    g[u].append([v, t])
    g[v].append([u, t])
    for i in range(w):
    u, v, t = map(int, input().split())
    g[u].append([v, -t])
    if spfa():
    print("YES")
    else:
    print("NO")
    
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/193704.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • IntelliJ IDEA全局内容搜索和替换

    IntelliJ IDEA全局内容搜索和替换在做项目时,有时会在整个项目里或指定文件夹下进行全局搜索和替换,这是一个很方便功能。使用方法如下:一、全局搜索1、使用快捷键Ctrl+Shift+F打开搜索窗口,或者通过点击Edit–>Find–>Findinpath打开搜索窗口,如下图:2、搜索界面如下,主要分为上中下三部分,上部主要为搜索条件(要搜索的内容、范围、方式等),中间部分为包含搜索内容的文件列表,点击单个文件可以在下面部分

  • 编译java程序需要使用命令_编译Java程序需要使用____命令。

    编译java程序需要使用命令_编译Java程序需要使用____命令。—myglasses?—Yes,Isawthemonyourbedaminuteago.A.DoyouseeB.HadyouseenC.WouldyouseeD.H_______acertaindoubtamongthepeopleastothepracticalvalueoftheproject.A.IthasB.TheyhavHer…

  • Java在字符串中查找匹配的子字符串

    Java在字符串中查找匹配的子字符串Java在字符串中查找匹配的子字符串

  • OpenCV 人脸识别LBPH算法分析

    OpenCV 人脸识别LBPH算法分析一、背景及理论基础人脸识别是指将一个需要识别的人脸和人脸库中的某个人脸对应起来(类似于指纹识别),目的是完成识别功能,该术语需要和人脸检测进行区分,人脸检测是在一张图片中把人脸定位出来,完成的是搜寻的功能。从OpenCV2.4开始,加入了新的类FaceRecognizer,该类用于人脸识别,使用它可以方便地进行相关识别实验。原始的LBP算子定义为在3*3的窗口内,以窗口中心像素为阈值,将相邻的8…

  • 华为三层交换机配置vlanif_华为三层交换机查看路由表

    华为三层交换机配置vlanif_华为三层交换机查看路由表实验拓扑实验需求1、C1与C3属于VLAN10,C2与C4属于VLAN20,在SW1上创建VLAN100做上行VLAN2、在SW1上终结所有VLAN3、在所有VLAN成员使用DHCP获取IP4、全网互通IP规划VLAN10:192.168.10.0/24VLAN20:192.168.20.0/24VLAN100:192.168.100.10/24R1G0/0/0:192…

  • pycharm如何安装python环境_pycharm怎么安装「建议收藏」

    pycharm如何安装python环境_pycharm怎么安装「建议收藏」安装方法:1、安装配置好Python环境;2、从官网下载pycharm安装程序;3、直接双击下载好的exe文件,进入安装向导界面,按照指示一步步操作;4、点击Install进行安装,等待安装完成后,点击Finish结束安装即可。本教程操作环境:windows7系统、Python3.5.2版本、DellG3电脑。首先我们来安装python1、首先进入网站下载:点击打开链接(或自己输入网址http…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号