蒟蒻求助spfa(它死了
  • 板块学术版
  • 楼主Jasonsheng
  • 当前回复9
  • 已保存回复9
  • 发布时间2022/5/7 22:08
  • 上次更新2023/10/28 01:57:08
查看原帖
蒟蒻求助spfa(它死了
95537
Jasonsheng楼主2022/5/7 22:08

题目背景: 宇宙中有一些虫洞,通过虫洞可以让时间瞬间增加或减少一个值(同时空间也到达另一个位置),如果能通过一系列虫洞,使得时间倒退,而空间上回到出发点,那么就是真正的回到过去。这种路径就称为类时闭曲线

输入格式

第一行三个正整数T,n,m(T<=5,n<=3000,m<=200000),表示数据组数,星球的个数,虫洞的个数

后面有T*m行,每m行表示一组数据。每行3个整数u,v,w(1<=u,v<=n,-1000<=w<=1000),表示星球u到星球v有一个虫洞(单向的),通过虫洞时间可以增加w(w为负表示减少)

输出格式

T行每行一个字符串,如果存在类时闭曲线,并且可以到达这条闭曲线,则输出Singular; 否则输出Normal(初始时在星球1上)。

2022/5/7 22:08
加载中...