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)


相关推荐

  • ExaGrid获得+73的净推荐值

    ExaGrid获得+73的净推荐值根据NPS标准,此分数值被归为“优秀”马萨诸塞州韦斯特伯鲁–(美国商业资讯)–备份用超融合二级存储器领先供应商ExaGrid®今日宣布,在近日开展的净推荐值(NPS)调查中,该公司的NPS为+73。NPS客户忠诚度指标用于测评现有客户向同行推荐供应商产品或服务的可能性。得到的NPS分数可能低至-100或高达+100。ExaGrid的大多数竞争对手的NPS介于+10和+20之间,而Exa…

  • Odin Inspector 系列教程 — 初识 OdinWindow「建议收藏」

    Odin Inspector 系列教程 — 初识 OdinWindow「建议收藏」笔者以往在使用一些插件的时候经常会看上面这种多炫酷的插件操作界面,常常羡慕不已,如今有了Odin,自己也可以简简单单的实现这些炫酷的效果了,下面笔者就带大家初识OdinWindow。创建一个Window不积跬步无以至千里,我们先从最简单的创建一个Window开始,只需要自定义一类并继承OdinEditorWindow即可publiccl…

  • mtk手机维修_mtk平台手机

    mtk手机维修_mtk平台手机默认分类2009-10-1902:21:04阅读1252评论7字号:大中小  MTK用电池不开机,用外用电源能开机的维修方法:MTK用电池不开机,用外用电源能开机的维修方法,我们可以找到VBAT也就是电触B+通电源的sas31233l213321+987+9877777777777777777777777777777777777777777777777777

    2022年10月28日
  • 详解 ManualResetEvent(转)

    详解 ManualResetEvent(转)原文:http://www.cnblogs.com/li-peng/p/3291306.html今天详细说一下ManualResetEvent它可以通知一个或多个正在等待的线程已发生事件,允许线程通过发信号互相通信,来控制线程是否可心访问资源当一个线程开始一个活动(此活动必须完成后,其他线程才能开始)时,它调用Reset以将ManualResetEvent置于非终止状…

  • [ Laravel 5.1 文档 ] 服务 —— 帮助函数

    [ Laravel 5.1 文档 ] 服务 —— 帮助函数

    2021年10月23日
  • 使用memcached加速web应用实例

    使用memcached加速web应用实例

发表回复

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

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